Background

“Good child, if you were offered wealth for three lifetimes, would you study?”

Today, 玛德琳 and 坏德琳 came to a fantastical machine. Inside the machine are balls of four colors, each with its own use. Blue bumpers are the most basic: bouncing on one grants you one dash. Pink bumpers are an upgraded version: bouncing on one grants you two dashes. Bouncing on a white bumper does not grant any dashes. A yellow bumper grows spikes after being bounced on once, and you cannot touch it again afterwards.

The levels inside can be described by a sequence of colors. 玛德琳 and 坏德琳 have been playing inside for a long time, but they still have not cleared the first level. 玛德琳 becomes so frustrated that she bursts into tears! She decides to cheat using a trainer! This trainer is rather special: it can only modify white and yellow bumpers, and can only turn them into blue and pink bumpers. Moreover, the position of the bumper modified each time is fixed. When 坏德琳 learns of this, she decides to stop 玛德琳 from cheating, so she hacks the trainer and gains permission to change the colors of yellow bumpers. Meanwhile, 玛德琳 believes that a string of identical bumpers makes a level easier. She defines a level's easiness as the maximum length of a segment of a single color. 玛德琳 wants to maximize this value, while 坏德琳 wants to minimize it.

Description

Alice and Bob play a game on a sequence of length $n$. Each element of the sequence can only have value $0$ or $1$, and the time at which each element's value is determined is fixed before the game begins.

You are given sequences $p$ and $a$ of length $n$, where $p$ is a permutation of $1\dots n$, and $a_i\in\{-2,-1,0,1\}$.

The value of the $i$-th element of the sequence is determined at time $p_i$, according to the following rules:

• If $a_i=0$, the element is assigned the value $0$;
• If $a_i=1$, the element is assigned the value $1$;
• If $a_i=-1$, Alice decides the element's value at that time;
• If $a_i=-2$, Bob decides the element's value at that time.

Before the game begins, both Alice and Bob know the sequences $p$ and $a$. The game lasts for $n$ time steps. At time $k$, the value at the position $i$ satisfying $p_i=k$ is determined; after all $n$ time steps, the value of each element of the sequence has been determined exactly once.

A monochromatic contiguous segment is defined as a pair $(l,r)$ satisfying $l\le r$, such that all elements from the $l$-th to the $r$-th have the same value. If it cannot be extended further in either direction (that is, $l=1$ or element $l-1$ has a different value, and $r=n$ or element $r+1$ has a different value), it is called a maximal monochromatic contiguous segment. The length of $(l,r)$ is $r-l+1$.

Alice wants to maximize the maximum length among all maximal monochromatic contiguous segments of the sequence after time $n$, while Bob wants to minimize this value.

You are given a positive integer $typ \in \{1,2\}$.

If $typ=1$, both players follow optimal strategies. Find the maximum length of a maximal monochromatic contiguous segment in the final sequence. It can be proved that the answer is uniquely determined.

If $typ=2$, you are additionally given a sequence $A$ of length $n$. Here, $A_i \in \{0,1\}$ specifies the decision made at time $i$ of the game: let $x$ be the unique positive integer among $1,2,\dots,n$ satisfying $p_x=i$, and assign the $x$-th element of the sequence the value $A_i$ (a cosmic ray may hit position $x$, causing $a_x,A_i \in \{0,1\}$ and $a_x \neq A_i$). For each $i=0,1,\dots,n$, find the length $ans_i$ of the longest monochromatic contiguous segment in the final sequence if the game follows the decisions in $A$ up to and including time $i$, and both players follow optimal strategies after time $i$ ends.

Input

This problem must be solved online.

The first line contains a positive integer $T$, the number of test cases.

There are $T$ test cases that follow. In each test case:

The first line contains two positive integers $n$ and $typ$.

The second line contains $n$ integers $p_1,p_2,\dots,p_n$.

The third line contains $n$ integers $a_1,a_2,\dots,a_n$.

If $typ=2$, the fourth line contains $n$ integers $A'_1,A'_2,\dots,A'_n$.

The actual value of $A_i$ is obtained by taking the bitwise XOR of $A'_i$ and $ans_{i-1}$, then taking the result modulo $2$.

Output

For each test case:

If $typ=1$, output a single integer on one line: the length of the longest monochromatic contiguous segment in the final sequence when both players follow optimal strategies.

If $typ=2$, output $n+1$ integers on one line. For each $i=0,1,\dots,n$, output the length of the longest monochromatic contiguous segment in the final sequence if the game follows the decisions in $A$ up to and including time $i$, and both players follow optimal strategies after time $i$ ends.

Examples

Input 1

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

Output 1

3

Note

$p=[3,1,2]$ means $p_1=3,\ p_2=1,\ p_3=2$: element $1$ is determined at time $3$, element $2$ at time $1$, and element $3$ at time $2$. Thus, the chronological order is:

• Time $1$: determine element $2$ ($a_2=-2$, decided by Bob);
• Time $2$: determine element $3$ ($a_3=-1$, decided by Alice);
• Time $3$: determine element $1$ ($a_1=-1$, decided by Alice).

Alice wants to make the longest monochromatic segment as long as possible, while Bob wants to make it as short as possible. Although Bob moves first, he controls only element $2$, right in the middle; Alice controls elements $1$ and $3$ at the two ends.

If Bob sets element $2$ to $0$, Alice can also set both elements $1$ and $3$ to $0$, producing the final sequence 0 0 0, whose longest monochromatic segment has length $3$. If Bob sets element $2$ to $1$, Alice likewise chooses $1$ for both, producing the final sequence 1 1 1, whose longest monochromatic segment still has length $3$.

Both of Bob's choices lead to exactly the same result, so he cannot bring the answer below $3$. Alice can at most make the entire sequence monochromatic, so the answer is $3$.

Input 2

1
2 1
2 1
-1 -1

Output 2

2

Note

$p=[2,1]$ means $p_1=2,\ p_2=1$: element $1$ is determined at time $2$, and element $2$ at time $1$. Both elements have $a$ values equal to $-1$, so both are decided by Alice:

• Time $1$: determine element $2$ ($a_2=-1$, decided by Alice);
• Time $2$: determine element $1$ ($a_1=-1$, decided by Alice).

Alice wants to maximize the length of the longest monochromatic segment. Since she decides both elements, she can simply give them the same value, obtaining 0 0 or 1 1. In either case, $(1,2)$ is a maximal monochromatic contiguous segment of length $2$. Since the entire sequence has length only $2$, this is also the best result she can achieve.

Input 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

Output 3

1
2 2 3 2 2
2

Constraints

Appropriate subtask dependencies are enabled for this problem.

For all test cases, it is guaranteed that:

• $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$ is a permutation of $1\dots n$.

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

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

Special property A: It is guaranteed that $a_i\in\{0,1\}$.

Special property B: It is guaranteed that $p$ and $a$ are generated randomly from the sequences of length $n$ satisfying the constraints.

Note: Subtasks $3,4,5,8,9$ depend on subtask $2$.