Contexto

“Minha boa criança, se te oferecessem a riqueza de três vidas, estudarias?”

Hoje, 玛德琳 e 坏德琳 chegaram diante de uma máquina fantástica. Dentro da máquina há bolas de quatro cores, cada uma com a sua função. As bolas azuis são as mais básicas: ao saltar sobre uma delas, ganhas a capacidade de fazer uma arrancada. As bolas cor-de-rosa são uma versão melhorada: ao saltar sobre uma delas, ganhas duas arrancadas. Saltar sobre uma bola branca não concede nenhuma arrancada. Depois de saltares uma vez sobre uma bola amarela, ela ganha espinhos e já não podes voltar a tocar-lhe.

Os níveis desta máquina podem ser descritos por uma sequência de cores. 玛德琳 e 坏德琳 jogaram durante muito tempo, mas ainda não conseguiram passar do primeiro nível. 玛德琳 ficou tão aflita que começou a chorar! Decidiu fazer batota usando um modificador! Este modificador é especial: só pode alterar bolas brancas e amarelas, só pode transformá-las em bolas azuis ou cor-de-rosa, e a posição da bola alterada em cada ocasião está determinada. Quando 坏德琳 descobriu isto, decidiu impedir 玛德琳 de fazer batota. Por isso, pirateou o modificador e obteve permissão para alterar a cor das bolas amarelas. Entretanto, 玛德琳 considera que uma sequência de bolas iguais torna o nível mais fácil. Define a facilidade de um nível como o maior comprimento de um segmento de bolas da mesma cor. 玛德琳 quer maximizar este valor, enquanto 坏德琳 quer minimizá-lo.

Descrição do problema

Alice e Bob jogam numa sequência de comprimento $n$. O valor de cada elemento da sequência só pode ser $0$ ou $1$, e o instante em que o valor de cada elemento será definido já está determinado antes do início do jogo.

São dadas as sequências $p$ e $a$, de comprimento $n$, em que $p$ é uma permutação de $1\dots n$ e $a_i\in\{-2,-1,0,1\}$.

O valor do $i$-ésimo elemento da sequência é definido no instante $p_i$, segundo as seguintes regras:

• Se $a_i=0$, atribui-se o valor $0$ a esse elemento;
• Se $a_i=1$, atribui-se o valor $1$ a esse elemento;
• Se $a_i=-1$, Alice decide o valor desse elemento nesse instante;
• Se $a_i=-2$, Bob decide o valor desse elemento nesse instante.

Antes do início do jogo, tanto Alice como Bob conhecem as sequências $p$ e $a$. O jogo decorre ao longo de $n$ instantes. No instante $k$, define-se o valor da posição $i$ que satisfaz $p_i=k$; após os $n$ instantes, o valor de cada elemento da sequência foi definido exatamente uma vez.

Um segmento contíguo monocromático é definido como um par $(l,r)$ que satisfaz $l\le r$ e no qual todos os elementos do $l$-ésimo ao $r$-ésimo têm o mesmo valor. Se não puder ser prolongado nem para a esquerda nem para a direita (isto é, $l=1$ ou o elemento $l-1$ tem um valor diferente dos seus elementos, e $r=n$ ou o elemento $r+1$ tem um valor diferente dos seus elementos), chama-se um segmento contíguo monocromático maximal. O comprimento de $(l,r)$ é $r-l+1$.

Alice quer maximizar o maior comprimento entre todos os segmentos contíguos monocromáticos maximais da sequência após o instante $n$, enquanto Bob quer minimizar esse valor.

É dado um inteiro positivo $typ \in \{1,2\}$.

Se $typ=1$, ambos os jogadores atuam segundo estratégias ótimas. Determina o maior comprimento dos segmentos contíguos monocromáticos maximais da sequência final. Pode provar-se que a resposta é determinada de forma única.

Se $typ=2$, é também dada uma sequência $A$ de comprimento $n$. O valor $A_i \in \{0,1\}$ indica que a decisão tomada no instante $i$ do jogo é a seguinte: seja $x$ o único inteiro positivo entre $1,2,\dots,n$ que satisfaz $p_x=i$; atribui-se o valor $A_i$ ao $x$-ésimo elemento da sequência (é possível que um raio cósmico atinja a posição $x$, fazendo com que $a_x,A_i \in \{0,1\}$ e $a_x \neq A_i$). Para cada $i=0,1,\dots,n$, determina o comprimento $ans_i$ do segmento contíguo monocromático mais longo da sequência final, se todas as decisões até ao instante $i$, inclusive, seguirem a sequência $A$ e, após o fim do instante $i$, ambos os jogadores atuarem segundo estratégias ótimas.

Entrada

Este problema exige processamento online.

A primeira linha contém um inteiro positivo $T$, que indica o número de casos de teste.

Seguem-se $T$ casos de teste. Em cada caso de teste:

A primeira linha contém dois inteiros positivos $n$ e $typ$.

A segunda linha contém $n$ inteiros $p_1,p_2,\dots,p_n$.

A terceira linha contém $n$ inteiros $a_1,a_2,\dots,a_n$.

Se $typ=2$, a quarta linha contém $n$ inteiros $A'_1,A'_2,\dots,A'_n$.

O verdadeiro valor de $A_i$ é o resultado de aplicar o XOR bit a bit entre $A'_i$ e $ans_{i-1}$ e, em seguida, tomar o resultado módulo $2$.

Saída

Para cada caso de teste:

Se $typ=1$, escreve numa linha um inteiro: o comprimento do segmento contíguo monocromático mais longo da sequência final quando ambos os jogadores atuam segundo estratégias ótimas.

Se $typ=2$, escreve numa linha $n+1$ inteiros: para cada $i=0,1,\dots,n$, o comprimento do segmento contíguo monocromático mais longo da sequência final, se todas as decisões até ao instante $i$, inclusive, seguirem a sequência $A$ e, após o fim do instante $i$, ambos os jogadores atuarem segundo estratégias ótimas.

Exemplos

Entrada 1

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

Saída 1

3

Nota

$p=[3,1,2]$ significa que $p_1=3,\ p_2=1,\ p_3=2$: o valor do $1$-º elemento é definido no instante $3$, o do $2$-º elemento no instante $1$ e o do $3$-º elemento no instante $2$. Assim, a ordem dos instantes é:

• Instante $1$: define-se o valor do $2$-º elemento ($a_2=-2$, decidido por Bob);
• Instante $2$: define-se o valor do $3$-º elemento ($a_3=-1$, decidido por Alice);
• Instante $3$: define-se o valor do $1$-º elemento ($a_1=-1$, decidido por Alice).

Alice quer que o segmento monocromático mais longo seja tão comprido quanto possível, enquanto Bob quer que seja tão curto quanto possível. Embora Bob jogue primeiro, só controla o $2$-º elemento, situado no meio; Alice controla os elementos das duas extremidades, o $1$-º e o $3$-º.

Se Bob definir o $2$-º elemento como $0$, Alice pode definir também o $1$-º e o $3$-º como $0$, obtendo a sequência final 0 0 0, cujo segmento monocromático mais longo tem comprimento $3$. Se Bob definir o $2$-º elemento como $1$, Alice escolhe igualmente $1$ para ambos, obtendo a sequência final 1 1 1, cujo segmento monocromático mais longo continua a ter comprimento $3$.

As duas escolhas de Bob conduzem exatamente ao mesmo resultado: ele não consegue reduzir a resposta abaixo de $3$. Por outro lado, Alice consegue, no máximo, tornar toda a sequência monocromática, pelo que a resposta é $3$.

Entrada 2

1
2 1
2 1
-1 -1

Saída 2

2

Nota

$p=[2,1]$ significa que $p_1=2,\ p_2=1$: o valor do $1$-º elemento é definido no instante $2$ e o do $2$-º elemento no instante $1$. Os valores de $a$ de ambos os elementos são $-1$, pelo que ambos são decididos por Alice:

• Instante $1$: define-se o valor do $2$-º elemento ($a_2=-1$, decidido por Alice);
• Instante $2$: define-se o valor do $1$-º elemento ($a_1=-1$, decidido por Alice).

Alice quer maximizar o comprimento do segmento monocromático mais longo. Como decide os valores de ambos os elementos, basta atribuir-lhes o mesmo valor para obter 0 0 ou 1 1. Nesse caso, $(1,2)$ é um segmento contíguo monocromático maximal de comprimento $2$. Como o comprimento total da sequência é apenas $2$, este é também o melhor resultado que ela pode alcançar.

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

Saída 3

1
2 2 3 2 2
2

Restrições

Este problema utiliza dependências apropriadas entre subtarefas.

Para todos os dados, garante-se 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$ é uma permutação de $1\dots n$.

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

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

Propriedade especial A: garante-se que $a_i\in\{0,1\}$.

Propriedade especial B: garante-se que $p$ e $a$ são geradas aleatoriamente entre as sequências de comprimento $n$ que satisfazem as restrições.

Atenção: as subtarefas $3,4,5,8,9$ dependem da subtarefa $2$.