Hintergrund

„Liebes Kind, wenn ich dir Reichtum für drei Leben schenke, würdest du dann lernen?“

Heute stehen 玛德琳 und 坏德琳 vor einer fantastischen Maschine. In der Maschine gibt es Kugeln in vier Farben, die jeweils unterschiedliche Funktionen haben. Blaue Sprungkugeln sind die einfachsten: Wenn du von einer abspringst, erhältst du die Fähigkeit zu einem Dash. Rosa Sprungkugeln sind die verbesserte Version: Wenn du von einer abspringst, erhältst du zwei Dashes. Weiße Sprungkugeln geben dir beim Abspringen keinen Dash. Gelben Sprungkugeln wachsen nach dem ersten Absprung Stacheln, und danach darfst du sie nicht mehr berühren.

Die Level darin lassen sich durch eine Folge von Farben beschreiben. 玛德琳 und 坏德琳 haben schon lange darin gespielt, aber noch nicht einmal das erste Level geschafft. 玛德琳 bricht vor Verzweiflung in Tränen aus! Sie beschließt, mithilfe eines Cheatprogramms zu schummeln! Dieses Cheatprogramm ist besonders: Es kann nur weiße und gelbe Sprungkugeln verändern, und zwar nur in blaue oder rosa Sprungkugeln; außerdem steht bei jeder Änderung die Position der zu verändernden Kugel fest. Als 坏德琳 davon erfährt, beschließt sie, 玛德琳 am Schummeln zu hindern. Deshalb hackt sie das Cheatprogramm und erlangt die Berechtigung, die Farbe der gelben Sprungkugeln zu ändern. 玛德琳 findet außerdem, dass eine Reihe gleicher Sprungkugeln ein Level einfacher macht. Sie definiert die Einfachheit eines Levels als die maximale Länge eines gleichfarbigen Abschnitts. 玛德琳 möchte diesen Wert maximieren, während 坏德琳 ihn minimieren möchte.

Aufgabenstellung

Alice und Bob spielen ein Spiel auf einer Folge der Länge $n$. Jedes Element der Folge kann nur den Wert $0$ oder $1$ haben, und der Zeitpunkt, zu dem der Wert jedes Elements festgelegt wird, steht bereits vor Spielbeginn fest.

Gegeben sind Folgen $p$ und $a$ der Länge $n$, wobei $p$ eine Permutation von $1\dots n$ ist und $a_i\in\{-2,-1,0,1\}$ gilt.

Der Wert des $i$-ten Elements der Folge wird zum Zeitpunkt $p_i$ nach den folgenden Regeln festgelegt:

• Falls $a_i=0$, wird diesem Element der Wert $0$ zugewiesen;
• falls $a_i=1$, wird diesem Element der Wert $1$ zugewiesen;
• falls $a_i=-1$, entscheidet Alice zu diesem Zeitpunkt über den Wert dieses Elements;
• falls $a_i=-2$, entscheidet Bob zu diesem Zeitpunkt über den Wert dieses Elements.

Vor Spielbeginn kennen sowohl Alice als auch Bob die Folgen $p$ und $a$. Das Spiel umfasst insgesamt $n$ Zeitpunkte. Zum Zeitpunkt $k$ wird der Wert an derjenigen Position $i$ festgelegt, für die $p_i=k$ gilt. Nach diesen $n$ Zeitpunkten wurde der Wert jedes Elements der Folge genau einmal festgelegt.

Ein zusammenhängender gleichfarbiger Abschnitt ist ein Paar $(l,r)$ mit $l\le r$, bei dem alle Elemente vom $l$-ten bis zum $r$-ten Element denselben Wert haben. Lässt sich dieser Abschnitt weder nach links noch nach rechts erweitern (das heißt, es gilt $l=1$ oder das Element an Position $l-1$ hat einen anderen Wert, und es gilt $r=n$ oder das Element an Position $r+1$ hat einen anderen Wert), so heißt er maximaler zusammenhängender gleichfarbiger Abschnitt. Die Länge von $(l,r)$ ist $r-l+1$.

Alice möchte nach dem Zeitpunkt $n$ das Maximum der Längen aller maximalen zusammenhängenden gleichfarbigen Abschnitte der Folge maximieren, während Bob diesen Wert minimieren möchte.

Gegeben ist eine positive ganze Zahl $typ \in \{1,2\}$.

Falls $typ=1$, spielen beide nach einer optimalen Strategie. Bestimme das Maximum der Längen der maximalen zusammenhängenden gleichfarbigen Abschnitte der endgültigen Folge. Es lässt sich beweisen, dass die Antwort eindeutig bestimmt ist.

Falls $typ=2$, ist zusätzlich eine Folge $A$ der Länge $n$ gegeben. Dabei gilt $A_i \in \{0,1\}$, und die zum Zeitpunkt $i$ des Spiels getroffene Entscheidung ist wie folgt: Sei $x$ die eindeutige positive ganze Zahl aus $1,2,\dots,n$ mit $p_x=i$. Dem $x$-ten Element der Folge wird der Wert $A_i$ zugewiesen (es kann vorkommen, dass kosmische Strahlung die Position $x$ trifft, sodass $a_x,A_i \in \{0,1\}$ und $a_x \neq A_i$ gelten). Bestimme für jedes $i=0,1,\dots,n$ die Länge $ans_i$ des längsten zusammenhängenden gleichfarbigen Abschnitts der endgültigen Folge, wenn bis einschließlich Zeitpunkt $i$ die Entscheidungen der Folge $A$ befolgt werden und beide Spieler nach dem Ende von Zeitpunkt $i$ nach einer optimalen Strategie spielen.

Eingabe

Diese Aufgabe erzwingt eine Online-Verarbeitung.

Die erste Zeile enthält eine positive ganze Zahl $T$, die Anzahl der Testfälle.

Es folgen insgesamt $T$ Testfälle. Jeder Testfall hat die folgende Form:

Die erste Zeile enthält zwei positive ganze Zahlen $n$ und $typ$.

Die zweite Zeile enthält $n$ ganze Zahlen $p_1,p_2,\dots,p_n$.

Die dritte Zeile enthält $n$ ganze Zahlen $a_1,a_2,\dots,a_n$.

Falls $typ=2$, enthält die vierte Zeile $n$ ganze Zahlen $A'_1,A'_2,\dots,A'_n$.

Der tatsächliche Wert von $A_i$ ergibt sich, indem man $A'_i$ und $ans_{i-1}$ bitweise mit XOR verknüpft und das Ergebnis modulo $2$ nimmt.

Ausgabe

Für jeden Testfall:

Falls $typ=1$, gib in einer Zeile eine ganze Zahl aus: die Länge des längsten zusammenhängenden gleichfarbigen Abschnitts der endgültigen Folge, wenn beide Spieler nach einer optimalen Strategie spielen.

Falls $typ=2$, gib in einer Zeile $n+1$ ganze Zahlen aus. Diese geben für jedes $i=0,1,\dots,n$ die Länge des längsten zusammenhängenden gleichfarbigen Abschnitts der endgültigen Folge an, wenn bis einschließlich Zeitpunkt $i$ die Entscheidungen der Folge $A$ befolgt werden und beide Spieler nach dem Ende von Zeitpunkt $i$ nach einer optimalen Strategie spielen.

Beispiele

Eingabe 1

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

Ausgabe 1

3

Hinweis

$p=[3,1,2]$ bedeutet $p_1=3,\ p_2=1,\ p_3=2$: Der Wert des $1$-ten Elements wird zum Zeitpunkt $3$ festgelegt, der des $2$-ten Elements zum Zeitpunkt $1$ und der des $3$-ten Elements zum Zeitpunkt $2$. Die zeitliche Reihenfolge ist also:

• Zeitpunkt $1$: Der Wert des $2$-ten Elements wird festgelegt ($a_2=-2$, Bob entscheidet);
• Zeitpunkt $2$: Der Wert des $3$-ten Elements wird festgelegt ($a_3=-1$, Alice entscheidet);
• Zeitpunkt $3$: Der Wert des $1$-ten Elements wird festgelegt ($a_1=-1$, Alice entscheidet).

Alice möchte, dass der längste gleichfarbige Abschnitt möglichst lang ist, während Bob möchte, dass er möglichst kurz ist. Bob beginnt zwar, kontrolliert aber nur das $2$-te Element genau in der Mitte; Alice kontrolliert die beiden äußeren Elemente $1$ und $3$.

Wenn Bob das $2$-te Element auf $0$ setzt, kann Alice auch das $1$-te und das $3$-te Element auf $0$ setzen. Die endgültige Folge ist dann 0 0 0, und der längste gleichfarbige Abschnitt hat die Länge $3$. Setzt Bob das $2$-te Element auf $1$, wählt Alice ebenfalls für beide den Wert $1$. Die endgültige Folge ist dann 1 1 1, und der längste gleichfarbige Abschnitt hat weiterhin die Länge $3$.

Bobs beide Möglichkeiten führen zum gleichen Ergebnis; er kann die Antwort nicht unter $3$ senken. Alice kann ihrerseits höchstens die gesamte Folge gleichfarbig machen. Daher ist die Antwort $3$.

Eingabe 2

1
2 1
2 1
-1 -1

Ausgabe 2

2

Hinweis

$p=[2,1]$ bedeutet $p_1=2,\ p_2=1$: Der Wert des $1$-ten Elements wird zum Zeitpunkt $2$ festgelegt und der des $2$-ten Elements zum Zeitpunkt $1$. Die $a$-Werte beider Elemente sind $-1$, also entscheidet Alice über beide:

• Zeitpunkt $1$: Der Wert des $2$-ten Elements wird festgelegt ($a_2=-1$, Alice entscheidet);
• Zeitpunkt $2$: Der Wert des $1$-ten Elements wird festgelegt ($a_1=-1$, Alice entscheidet).

Alice möchte die Länge des längsten gleichfarbigen Abschnitts maximieren. Da sie über beide Elemente entscheidet, muss sie ihnen nur denselben Wert zuweisen und erhält 0 0 oder 1 1. Dann ist $(1,2)$ ein maximaler zusammenhängender gleichfarbiger Abschnitt der Länge $2$. Da die gesamte Folge nur die Länge $2$ hat, ist dies auch das beste Ergebnis, das sie erzielen kann.

Eingabe 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

Ausgabe 3

1
2 2 3 2 2
2

Beschränkungen

Für diese Aufgabe sind sinnvolle Abhängigkeiten zwischen Teilaufgaben aktiviert.

Für alle Testfälle gilt:

• $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$ ist eine Permutation von $1\dots n$.

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

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

Besondere Eigenschaft A: Es gilt $a_i\in\{0,1\}$.

Besondere Eigenschaft B: $p$ und $a$ werden zufällig aus den Folgen der Länge $n$ erzeugt, die die Beschränkungen erfüllen.

Hinweis: Die Teilaufgaben $3,4,5,8,9$ hängen von Teilaufgabe $2$ ab.