題目背景

「好孩子，假如給你三生三世的財富，學否？」

今天，瑪德琳和壞德琳來到了一個夢幻的機器面前。機器裡面有四種顏色的球，各有各的用處。藍色彈球是最基礎的彈球，你彈上去會獲得一次衝刺能力。粉色彈球是加強版，你彈上去會獲得兩次衝刺。白色彈球彈上去不能獲得衝刺。黃色彈球彈了一次之後會長出刺，並且以後你不能再接觸它。

這裡面的關卡可以透過一個顏色序列來描述。瑪德琳和壞德琳在裡面玩了很久，但還沒通過第一關。於是瑪德琳急哭了！她決定透過修改器作弊！這個修改器很特別，只能修改白彈球和黃彈球，且只能修改成藍彈球和粉彈球，而且每一次被修改的彈球位置是確定的。而壞德琳得知了此事，她決定阻止瑪德琳作弊，所以駭入了這個修改器，獲得了修改黃彈球顏色的權限。同時，瑪德琳認為，一連串相同的彈球會讓關卡變得簡單。她認為一個關卡的簡單度是同色段長度的最大值。瑪德琳想要最大化這個值，而壞德琳想要最小化這個值。

題目敘述

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$ 為唯一滿足 $p_x=i$ 的 $1,2,\dots,n$ 中的正整數，將序列的第 $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$ 依賴。