題目背景

「乖小朋友，假如畀你三生三世嘅財富，學唔學？」

今日，瑪德琳同壞德琳嚟到一部夢幻嘅機器面前。機器入面有四種顏色嘅波，各有各嘅用途。藍色彈波係最基本嘅彈波，你彈上去就會得到一次衝刺能力。粉紅色彈波係加強版，你彈上去就會得到兩次衝刺。彈上白色彈波唔會得到衝刺。黃色彈波彈過一次之後就會生出刺，之後你就唔可以再掂佢。

入面嘅關卡可以用一個顏色序列嚟描述。瑪德琳同壞德琳喺入面玩咗好耐，但仲未過到第一關。於是瑪德琳急到喊咗！佢決定用修改器作弊！呢個修改器好特別，只可以修改白色彈波同黃色彈波，而且只可以改成藍色彈波同粉紅色彈波，每次會修改邊個位置嘅彈波亦都係定好咗嘅。壞德琳知道咗呢件事之後，決定阻止瑪德琳作弊，所以入侵咗呢個修改器，得到修改黃色彈波顏色嘅權限。同時，瑪德琳覺得，一連串相同嘅彈波會令關卡變得簡單。佢認為一個關卡嘅簡單度就係同色段長度嘅最大值。瑪德琳想令呢個值盡量大，而壞德琳就想令呢個值盡量細。

題目描述

Alice 同 Bob 喺一個長度為 $n$ 嘅序列上進行博弈。序列入面每個元素嘅值只可以係 $0$ 或 $1$，而每個元素喺邊個時刻取值，喺遊戲開始之前就已經定好咗。

畀定長度為 $n$ 嘅序列 $p$ 同 $a$，當中 $p$ 係 $1\dots n$ 嘅一個排列，$a_i\in\{-2,-1,0,1\}$。

序列嘅第 $i$ 個元素會喺第 $p_i$ 個時刻確定取值，規則如下：

• 如果 $a_i=0$，就將呢個元素賦值為 $0$；
• 如果 $a_i=1$，就將呢個元素賦值為 $1$；
• 如果 $a_i=-1$，呢個元素嘅值就由 Alice 喺嗰個時刻決定；
• 如果 $a_i=-2$，呢個元素嘅值就由 Bob 喺嗰個時刻決定。

遊戲開始之前，Alice 同 Bob 都知道序列 $p$ 同序列 $a$。遊戲一共進行 $n$ 個時刻，第 $k$ 個時刻會確定滿足 $p_i=k$ 嘅嗰個位置 $i$ 嘅取值；$n$ 個時刻結束之後，序列入面每個元素都啱啱好確定咗一次取值。

同色連續段定義為一個二元組 $(l,r)$，滿足 $l\le r$，而且由第 $l$ 個元素到第 $r$ 個元素嘅值全部相同；如果佢唔可以再向左或者向右延伸（即係 $l=1$ 或者第 $l-1$ 個元素同佢哋唔同，而且 $r=n$ 或者第 $r+1$ 個元素同佢哋唔同），就叫做一個極長同色連續段。$(l,r)$ 嘅長度係 $r-l+1$。

Alice 想令第 $n$ 個時刻之後，序列所有極長同色連續段長度嘅最大值盡量大，Bob 就想令呢個值盡量細。

畀定正整數 $typ \in \{1,2\}$。

如果 $typ=1$，雙方都會按最優策略行動，請求出最終序列極長同色連續段長度嘅最大值。可以證明答案係確定嘅。

如果 $typ=2$，會額外畀出長度為 $n$ 嘅序列 $A$。$A_i \in \{0,1\}$，表示博弈喺第 $i$ 個時刻作出嘅決策係：設 $x$ 係 $1,2,\dots,n$ 入面唯一滿足 $p_x=i$ 嘅正整數，將序列嘅第 $x$ 個元素賦值為 $A_i$（可能會有宇宙射線擊中第 $x$ 個位置，導致 $a_x,A_i \in \{0,1\}$ 而且 $a_x \neq A_i$ 嘅情況）。請對每個 $i=0,1,\dots,n$，求出如果喺第 $i$ 個時刻同之前都按照 $A$ 序列嘅決策博弈，而喺第 $i$ 個時刻結束之後雙方都按最優策略行動，最終序列入面最長同色連續段嘅長度 $ans_i$。

輸入格式

呢題強制在線

第一行包含一個正整數 $T$，表示數據組數。

跟住一共有 $T$ 組數據，每組數據如下：

第一行包含兩個正整數 $n$ 同 $typ$。

第二行包含 $n$ 個整數 $p_1,p_2,\dots,p_n$。

第三行包含 $n$ 個整數 $a_1,a_2,\dots,a_n$。

如果 $typ=2$，第四行包含 $n$ 個整數 $A'_1,A'_2,\dots,A'_n$。

真正嘅 $A_i$ 係將 $A'_i$ 同 $ans_{i-1}$ 做按位異或之後，再模 $2$ 嘅結果。

輸出格式

對每一組數據：

如果 $typ=1$，輸出一行一個整數，表示雙方都按最優策略行動嗰陣，最終序列入面最長同色連續段嘅長度。

如果 $typ=2$，輸出一行 $n+1$ 個整數，分別表示對於 $i=0,1,\dots,n$，如果喺第 $i$ 個時刻同之前都按照 $A$ 序列嘅決策博弈，而喺第 $i$ 個時刻結束之後雙方都按最優策略行動，最終序列入面最長同色連續段嘅長度。

樣例

輸入格式 1

1
3 1
3 1 2
-1 -2 -1

輸出格式 1

3

說明

$p=[3,1,2]$ 表示 $p_1=3,\ p_2=1,\ p_3=2$：第 $1$ 個元素喺第 $3$ 個時刻確定，第 $2$ 個元素喺第 $1$ 個時刻確定，第 $3$ 個元素喺第 $2$ 個時刻確定。所以時刻順序係：

• 時刻 $1$：確定第 $2$ 個元素（$a_2=-2$，由 Bob 決定）；
• 時刻 $2$：確定第 $3$ 個元素（$a_3=-1$，由 Alice 決定）；
• 時刻 $3$：確定第 $1$ 個元素（$a_1=-1$，由 Alice 決定）。

Alice 想令最長同色段盡可能長，Bob 就想令佢盡可能短。雖然 Bob 先行，但佢只控制正中間嘅第 $2$ 個元素；Alice 就控制第 $1$、$3$ 呢兩個端點元素。

Bob 將第 $2$ 個元素定為 $0$ 之後，Alice 可以將第 $1$、$3$ 個元素都定為 $0$，最終序列就係 0 0 0，最長同色段嘅長度係 $3$；如果 Bob 將第 $2$ 個元素定為 $1$，Alice 一樣全部揀 $1$，最終序列就係 1 1 1，最長同色段嘅長度仍然係 $3$。

Bob 呢兩種揀法得出嘅結果完全相同，佢冇辦法將答案壓低到 $3$ 以下；而 Alice 最多亦只可以令成個序列同色，所以答案係 $3$。

輸入格式 2

1
2 1
2 1
-1 -1

輸出格式 2

2

說明

$p=[2,1]$ 表示 $p_1=2,\ p_2=1$：第 $1$ 個元素喺第 $2$ 個時刻確定，第 $2$ 個元素喺第 $1$ 個時刻確定。兩個元素嘅 $a$ 值都係 $-1$，所以都由 Alice 決定：

• 時刻 $1$：確定第 $2$ 個元素（$a_2=-1$，由 Alice 決定）；
• 時刻 $2$：確定第 $1$ 個元素（$a_1=-1$，由 Alice 決定）。

Alice 想令最長同色段盡量長。兩個元素都由佢決定，佢只要將兩者賦成相同嘅值，就會得到 0 0 或 1 1，呢個時候 $(1,2)$ 就係長度為 $2$ 嘅極長同色連續段；而序列總長度只有 $2$，所以呢個亦都係佢可以得到嘅最好結果。

輸入格式 3

3
2 1
1 2
-1 -2
4 2
1 3 2 4
-1 0 -2 -1
1 0 0 1
3 1
3 1 2
0 0 1

輸出格式 3

1
2 2 3 2 2
2

數據範圍

呢題設有合理嘅子任務依賴。

對所有數據，保證：

• $1 \leq T \leq 2 \times 10^5$, $1\le n\le 2\times 10^5$, $1 \le typ \le 2$, $1 \leq \sum n \leq 2 \times 10^5$。

• $p$ 係 $1\dots n$ 嘅一個排列。

• $a_i\in\{-2,-1,0,1\}$。

• $A_i\in\{0,1\}$。

特殊性質 A：保證 $a_i\in\{0,1\}$。

特殊性質 B：保證 $p$ 同 $a$ 係喺長度為 $n$ 而且符合限制嘅序列之中隨機生成嘅。

注意：子任務 $2$ 係子任務 $3,4,5,8,9$ 所依賴嘅子任務。