Contexto

«Buen muchacho, si te ofreciera riquezas para tres vidas, ¿aprenderías?»

Hoy, 玛德琳 y 坏德琳 se han acercado a una máquina de ensueño. Dentro de la máquina hay bolas de cuatro colores, cada una con su propia utilidad. Las bolas azules son las más básicas: al rebotar en una de ellas, obtienes la capacidad de realizar un impulso. Las bolas rosas son una versión mejorada: al rebotar en una de ellas, obtienes dos impulsos. Rebotar en una bola blanca no te proporciona ningún impulso. A las bolas amarillas les salen pinchos después de rebotar una vez en ellas, y ya no puedes volver a tocarlas.

Los niveles de esta máquina se pueden describir mediante una secuencia de colores. 玛德琳 y 坏德琳 llevan mucho tiempo jugando, pero todavía no han superado el primer nivel. ¡玛德琳 se desespera y se echa a llorar! ¡Decide hacer trampas con un modificador! Este modificador es especial: solo puede modificar las bolas blancas y amarillas, y únicamente puede convertirlas en bolas azules o rosas; además, la posición de la bola que se modifica en cada ocasión está fijada. Cuando 坏德琳 se entera, decide impedir que 玛德琳 haga trampas, así que hackea el modificador y obtiene permiso para cambiar el color de las bolas amarillas. Por otra parte, 玛德琳 considera que una serie de bolas iguales hace que el nivel sea más sencillo. Define la sencillez de un nivel como la longitud máxima de un segmento del mismo color. 玛德琳 quiere maximizar este valor, mientras que 坏德琳 quiere minimizarlo.

Descripción

Alice y Bob juegan sobre una secuencia de longitud $n$. El valor de cada elemento de la secuencia solo puede ser $0$ o $1$, y el instante en que se asigna el valor de cada elemento está fijado antes de que comience el juego.

Se dan dos secuencias $p$ y $a$ de longitud $n$, donde $p$ es una permutación de $1\dots n$ y $a_i\in\{-2,-1,0,1\}$.

El valor del elemento $i$ de la secuencia se determina en el instante $p_i$, según las siguientes reglas:

• Si $a_i=0$, se asigna a ese elemento el valor $0$;
• si $a_i=1$, se asigna a ese elemento el valor $1$;
• si $a_i=-1$, Alice decide el valor de ese elemento en ese instante;
• si $a_i=-2$, Bob decide el valor de ese elemento en ese instante.

Antes de comenzar el juego, tanto Alice como Bob conocen las secuencias $p$ y $a$. El juego dura $n$ instantes. En el instante $k$ se determina el valor de la posición $i$ que satisface $p_i=k$; al terminar los $n$ instantes, el valor de cada elemento de la secuencia se habrá determinado exactamente una vez.

Un segmento contiguo del mismo color se define como un par $(l,r)$ tal que $l\le r$ y todos los elementos desde el $l$ hasta el $r$ tienen el mismo valor. Si no puede extenderse ni hacia la izquierda ni hacia la derecha (es decir, $l=1$ o el elemento $l-1$ tiene un valor distinto, y $r=n$ o el elemento $r+1$ tiene un valor distinto), se denomina segmento contiguo maximal del mismo color. La longitud de $(l,r)$ es $r-l+1$.

Alice quiere maximizar la longitud máxima entre todos los segmentos contiguos maximales del mismo color de la secuencia después del instante $n$, y Bob quiere minimizar ese valor.

Se da un entero positivo $typ \in \{1,2\}$.

Si $typ=1$, ambos jugadores actúan de forma óptima. Calcula la longitud máxima de los segmentos contiguos maximales del mismo color de la secuencia final. Se puede demostrar que la respuesta está determinada de forma única.

Si $typ=2$, se da además una secuencia $A$ de longitud $n$. $A_i \in \{0,1\}$ indica que la decisión tomada en el instante $i$ del juego es la siguiente: sea $x$ el único entero positivo entre $1,2,\dots,n$ que satisface $p_x=i$; se asigna al elemento $x$ de la secuencia el valor $A_i$ (es posible que un rayo cósmico incida en la posición $x$ y provoque una situación en la que $a_x,A_i \in \{0,1\}$ y $a_x \neq A_i$). Para cada $i=0,1,\dots,n$, calcula $ans_i$, la longitud del segmento contiguo más largo del mismo color en la secuencia final, si hasta el instante $i$, inclusive, se juega siguiendo las decisiones de la secuencia $A$ y, después de terminar el instante $i$, ambos jugadores actúan de forma óptima.

Entrada

Este problema debe resolverse obligatoriamente en línea.

La primera línea contiene un entero positivo $T$, el número de casos de prueba.

A continuación hay $T$ casos de prueba. En cada uno de ellos:

La primera línea contiene dos enteros positivos $n$ y $typ$.

La segunda línea contiene $n$ enteros $p_1,p_2,\dots,p_n$.

La tercera línea contiene $n$ enteros $a_1,a_2,\dots,a_n$.

Si $typ=2$, la cuarta línea contiene $n$ enteros $A'_1,A'_2,\dots,A'_n$.

El verdadero valor de $A_i$ se obtiene aplicando XOR bit a bit a $A'_i$ y $ans_{i-1}$, y tomando después el resultado módulo $2$.

Salida

Para cada caso de prueba:

Si $typ=1$, imprime una línea con un entero: la longitud del segmento contiguo más largo del mismo color en la secuencia final cuando ambos jugadores actúan de forma óptima.

Si $typ=2$, imprime una línea con $n+1$ enteros que indiquen, para cada $i=0,1,\dots,n$, la longitud del segmento contiguo más largo del mismo color en la secuencia final, si hasta el instante $i$, inclusive, se juega siguiendo las decisiones de la secuencia $A$ y, después de terminar el instante $i$, ambos jugadores actúan de forma óptima.

Ejemplos

Entrada 1

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

Salida 1

3

Nota

$p=[3,1,2]$ significa que $p_1=3,\ p_2=1,\ p_3=2$: el valor del elemento $1$ se determina en el instante $3$, el del elemento $2$ en el instante $1$ y el del elemento $3$ en el instante $2$. Por tanto, el orden de los instantes es:

• Instante $1$: se determina el elemento $2$ ($a_2=-2$, decide Bob);
• instante $2$: se determina el elemento $3$ ($a_3=-1$, decide Alice);
• instante $3$: se determina el elemento $1$ ($a_1=-1$, decide Alice).

Alice quiere que el segmento más largo del mismo color sea lo más largo posible, y Bob quiere que sea lo más corto posible. Aunque Bob actúa primero, solo controla el elemento $2$, situado en el centro; Alice controla los dos elementos de los extremos, $1$ y $3$.

Si Bob asigna $0$ al elemento $2$, Alice puede asignar también $0$ a los elementos $1$ y $3$, con lo que la secuencia final es 0 0 0 y la longitud del segmento más largo del mismo color es $3$. Si Bob asigna $1$ al elemento $2$, Alice también elige $1$ para ambos, con lo que la secuencia final es 1 1 1 y la longitud del segmento más largo del mismo color sigue siendo $3$.

Las dos elecciones de Bob conducen exactamente al mismo resultado, por lo que no puede reducir la respuesta por debajo de $3$. Por su parte, Alice como mucho puede conseguir que toda la secuencia tenga el mismo color, así que la respuesta es $3$.

Entrada 2

1
2 1
2 1
-1 -1

Salida 2

2

Nota

$p=[2,1]$ significa que $p_1=2,\ p_2=1$: el valor del elemento $1$ se determina en el instante $2$, y el del elemento $2$ en el instante $1$. El valor de $a$ de ambos elementos es $-1$, de modo que Alice decide ambos:

• Instante $1$: se determina el elemento $2$ ($a_2=-1$, decide Alice);
• instante $2$: se determina el elemento $1$ ($a_1=-1$, decide Alice).

Alice quiere maximizar la longitud del segmento más largo del mismo color. Como decide el valor de ambos elementos, basta con que les asigne el mismo valor para obtener 0 0 o 1 1. En ese caso, $(1,2)$ es un segmento contiguo maximal del mismo color de longitud $2$; como la longitud total de la secuencia es solo $2$, este es también el mejor resultado que puede conseguir.

Entrada 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

Salida 3

1
2 2 3 2 2
2

Restricciones

Este problema utiliza dependencias razonables entre subtareas.

Para todos los datos, se garantiza que:

• $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$ es una permutación de $1\dots n$.

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

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

Propiedad especial A: se garantiza que $a_i\in\{0,1\}$.

Propiedad especial B: se garantiza que $p$ y $a$ se generan aleatoriamente entre las secuencias de longitud $n$ que cumplen las restricciones.

Atención: las subtareas $3,4,5,8,9$ dependen de la subtarea $2$.