题目背景

“好孩子，假如给你三生三世的财富，学否？”

今天，玛德琳和坏德琳来到了一个梦幻的机器面前。机器里面有四种颜色的球，各有各的用处。蓝色弹球是最基础的弹球，你弹上去会获得一次冲刺能力。粉色弹球是加强版，你弹上去会获得两次冲刺。白色弹球弹上去不能获得冲刺。黄色弹球弹了一次之后会长出刺，并且以后你不能在接触它。

这里面的关卡可以通过一个颜色序列来描述。玛德琳和坏德琳在里面玩了很久，但还没通过第一关。于是玛德琳急哭了！她决定通过修改器作弊！这个修改器很特别，只能修改白弹球和黄弹球，且只能修改成蓝弹球和粉弹球，而且每一次被修改的弹球位置是确定的。而坏德琳得知了此事，她决定阻止玛德琳作弊，所以黑了这个修改器，获得了修改黄弹球颜色的权限。同时，玛德琳认为，一连串相同的弹球会让关卡变得简单。她认为一个关卡的简单度是同色段长度的最大值。玛德琳想要最大化这个值，而坏德琳想要最小化这个值。

题目描述

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

样例解释 #1

$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

样例解释 #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$ 依赖。