背景

「よい子よ、もし三度の生にわたる富を与えるとしたら、学ぶかね？」

今日、玛德琳と坏德琳は夢のような機械の前にやって来ました。機械の中には四つの色のボールがあり、それぞれ異なる役割があります。青いバンパーは最も基本的なもので、これに跳ね返されるとダッシュを一回使えるようになります。ピンクのバンパーは強化版で、これに跳ね返されるとダッシュを二回使えるようになります。白いバンパーに跳ね返されてもダッシュは得られません。黄色いバンパーは一度跳ね返すとトゲが生え、その後は触れることができなくなります。

この中のステージは、色の列で表すことができます。玛德琳と坏德琳は長い間遊んでいましたが、まだ最初のステージをクリアできていません。そこで玛德琳は焦って泣き出してしまいました！彼女は改造ツールで不正をすることにしました！この改造ツールは特殊で、白と黄色のバンパーしか変更できず、変更先も青とピンクのバンパーに限られ、さらに各回に変更されるバンパーの位置は決まっています。これを知った坏德琳は、玛德琳の不正を阻止することにし、改造ツールをハッキングして黄色いバンパーの色を変更する権限を得ました。また、玛德琳は、同じバンパーが連続するとステージが簡単になると考えています。彼女は、ステージの簡単さを、同じ色が連続する区間の長さの最大値と考えています。玛德琳はこの値を最大化したい一方、坏德琳は最小化したいと考えています。

問題文

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\le r$ を満たし、第 $l$ 要素から第 $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$ で制約を満たす列の中からランダムに生成されることが保証されます。

注意：小課題 $3,4,5,8,9$ は小課題 $2$ に依存します。