Tło fabularne

„Dobre dziecko, gdybym dał ci bogactwo na trzy wcielenia, czy zechciałbyś się uczyć?”

Dzisiaj 玛德琳 i 坏德琳 stanęły przed fantastyczną maszyną. W jej wnętrzu znajdują się kule w czterech kolorach, z których każdy ma inne zastosowanie. Niebieska kula jest najbardziej podstawowa: odbicie się od niej daje możliwość wykonania jednego zrywu. Różowa kula jest ulepszoną wersją: odbicie się od niej daje dwa zrywy. Odbicie się od białej kuli nie daje żadnego zrywu. Po jednym odbiciu od żółtej kuli wyrastają na niej kolce i od tej pory nie wolno jej już dotykać.

Poziom wewnątrz maszyny można opisać ciągiem kolorów. 玛德琳 i 坏德琳 grały tam już długo, ale wciąż nie przeszły pierwszego poziomu. 玛德琳 rozpłakała się z frustracji! Postanowiła oszukiwać za pomocą modyfikatora! Ten modyfikator jest szczególny: może zmieniać jedynie białe i żółte kule, i to tylko na niebieskie lub różowe, a pozycja kuli zmienianej w każdym kroku jest z góry ustalona. Gdy 坏德琳 się o tym dowiedziała, postanowiła powstrzymać 玛德琳 przed oszukiwaniem, więc zhakowała modyfikator i uzyskała uprawnienie do zmieniania koloru żółtych kul. 玛德琳 uważa też, że ciąg jednakowych kul ułatwia poziom. Według niej łatwość poziomu to największa długość jednokolorowego odcinka. 玛德琳 chce maksymalizować tę wartość, a 坏德琳 chce ją minimalizować.

Treść zadania

Alice i Bob grają w grę na ciągu długości $n$. Każdy element ciągu może mieć wyłącznie wartość $0$ lub $1$, a chwila ustalenia wartości każdego elementu jest wyznaczona jeszcze przed rozpoczęciem gry.

Dane są ciągi $p$ i $a$ długości $n$, przy czym $p$ jest permutacją $1\dots n$, a $a_i\in\{-2,-1,0,1\}$.

Wartość $i$-tego elementu ciągu zostaje ustalona w chwili $p_i$, zgodnie z następującymi regułami:

• Jeśli $a_i=0$, elementowi przypisuje się wartość $0$;
• jeśli $a_i=1$, elementowi przypisuje się wartość $1$;
• jeśli $a_i=-1$, wartość elementu wybiera w tej chwili Alice;
• jeśli $a_i=-2$, wartość elementu wybiera w tej chwili Bob.

Przed rozpoczęciem gry zarówno Alice, jak i Bob znają ciągi $p$ oraz $a$. Gra trwa $n$ chwil; w chwili $k$ ustala się wartość na tej pozycji $i$, dla której $p_i=k$. Po zakończeniu $n$ chwil wartość każdego elementu ciągu została ustalona dokładnie raz.

Jednokolorowy spójny odcinek to para $(l,r)$ spełniająca $l\le r$, taka że wszystkie elementy od $l$-tego do $r$-tego mają tę samą wartość. Jeśli nie można go przedłużyć ani w lewo, ani w prawo (czyli $l=1$ lub element na pozycji $l-1$ ma inną wartość oraz $r=n$ lub element na pozycji $r+1$ ma inną wartość), nazywamy go maksymalnym jednokolorowym spójnym odcinkiem. Długość $(l,r)$ wynosi $r-l+1$.

Alice chce maksymalizować największą długość spośród wszystkich maksymalnych jednokolorowych spójnych odcinków ciągu po chwili $n$, a Bob chce minimalizować tę wartość.

Dana jest dodatnia liczba całkowita $typ \in \{1,2\}$.

Jeśli $typ=1$, oboje stosują optymalne strategie. Wyznacz największą długość maksymalnego jednokolorowego spójnego odcinka w końcowym ciągu. Można udowodnić, że odpowiedź jest jednoznacznie określona.

Jeśli $typ=2$, dodatkowo dany jest ciąg $A$ długości $n$. Wartość $A_i \in \{0,1\}$ opisuje decyzję podjętą w chwili $i$ gry: niech $x$ będzie jedyną dodatnią liczbą całkowitą spośród $1,2,\dots,n$ spełniającą $p_x=i$; elementowi na pozycji $x$ przypisuje się wartość $A_i$ (może się zdarzyć, że promień kosmiczny trafi w pozycję $x$, przez co $a_x,A_i \in \{0,1\}$, ale $a_x \neq A_i$). Dla każdego $i=0,1,\dots,n$ wyznacz długość $ans_i$ najdłuższego jednokolorowego spójnego odcinka końcowego ciągu, jeżeli do chwili $i$ włącznie decyzje są podejmowane zgodnie z ciągiem $A$, a po zakończeniu chwili $i$ oboje stosują optymalne strategie.

Wejście

W tym zadaniu wymagane jest przetwarzanie online.

Pierwszy wiersz zawiera dodatnią liczbę całkowitą $T$, oznaczającą liczbę zestawów danych.

Następnie podanych jest $T$ zestawów danych. W każdym z nich:

Pierwszy wiersz zawiera dwie dodatnie liczby całkowite $n$ i $typ$.

Drugi wiersz zawiera $n$ liczb całkowitych $p_1,p_2,\dots,p_n$.

Trzeci wiersz zawiera $n$ liczb całkowitych $a_1,a_2,\dots,a_n$.

Jeśli $typ=2$, czwarty wiersz zawiera $n$ liczb całkowitych $A'_1,A'_2,\dots,A'_n$.

Rzeczywista wartość $A_i$ to wynik bitowego XOR liczb $A'_i$ i $ans_{i-1}$, wzięty modulo $2$.

Wyjście

Dla każdego zestawu danych:

Jeśli $typ=1$, wypisz w jednym wierszu jedną liczbę całkowitą: długość najdłuższego jednokolorowego spójnego odcinka końcowego ciągu, gdy oboje stosują optymalne strategie.

Jeśli $typ=2$, wypisz w jednym wierszu $n+1$ liczb całkowitych. Dla kolejnych $i=0,1,\dots,n$ mają one oznaczać długość najdłuższego jednokolorowego spójnego odcinka końcowego ciągu, jeżeli do chwili $i$ włącznie decyzje są podejmowane zgodnie z ciągiem $A$, a po zakończeniu chwili $i$ oboje stosują optymalne strategie.

Przykład

Wejście 1

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

Wyjście 1

3

Uwagi

$p=[3,1,2]$ oznacza $p_1=3,\ p_2=1,\ p_3=2$: wartość elementu $1$ ustala się w chwili $3$, elementu $2$ w chwili $1$, a elementu $3$ w chwili $2$. Kolejność jest więc następująca:

• Chwila $1$: ustalenie wartości elementu $2$ ($a_2=-2$, decyduje Bob);
• chwila $2$: ustalenie wartości elementu $3$ ($a_3=-1$, decyduje Alice);
• chwila $3$: ustalenie wartości elementu $1$ ($a_1=-1$, decyduje Alice).

Alice chce, aby najdłuższy jednokolorowy odcinek był jak najdłuższy, a Bob chce, aby był jak najkrótszy. Choć Bob wykonuje pierwszy ruch, kontroluje tylko środkowy element $2$, natomiast Alice kontroluje elementy $1$ i $3$ na obu końcach.

Jeśli Bob nada elementowi $2$ wartość $0$, Alice może nadać elementom $1$ i $3$ również wartość $0$. Końcowy ciąg to wtedy 0 0 0, a najdłuższy jednokolorowy odcinek ma długość $3$. Jeśli Bob nada elementowi $2$ wartość $1$, Alice również wybierze obie wartości $1$, otrzymując ciąg 1 1 1, w którym najdłuższy jednokolorowy odcinek nadal ma długość $3$.

Oba wybory Boba prowadzą do dokładnie tego samego wyniku: nie może on obniżyć odpowiedzi poniżej $3$. Z kolei Alice może co najwyżej sprawić, że cały ciąg będzie jednokolorowy, więc odpowiedź wynosi $3$.

Wejście 2

1
2 1
2 1
-1 -1

Wyjście 2

2

Uwagi

$p=[2,1]$ oznacza $p_1=2,\ p_2=1$: wartość elementu $1$ ustala się w chwili $2$, a elementu $2$ w chwili $1$. Oba elementy mają wartość $a$ równą $-1$, więc o obu decyduje Alice:

• Chwila $1$: ustalenie wartości elementu $2$ ($a_2=-1$, decyduje Alice);
• chwila $2$: ustalenie wartości elementu $1$ ($a_1=-1$, decyduje Alice).

Alice chce maksymalizować długość najdłuższego jednokolorowego odcinka. Ponieważ decyduje o obu elementach, wystarczy, że nada im jednakową wartość, uzyskując 0 0 lub 1 1. Wtedy $(1,2)$ jest maksymalnym jednokolorowym spójnym odcinkiem długości $2$. Cały ciąg ma długość tylko $2$, więc jest to najlepszy wynik, jaki może osiągnąć.

Wejście 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

Wyjście 3

1
2 2 3 2 2
2

Ograniczenia

W tym zadaniu obowiązują odpowiednie zależności między podzadaniami.

Dla wszystkich danych gwarantowane jest, że:

• $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$ jest permutacją $1\dots n$.

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

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

Własność specjalna A: gwarantowane jest $a_i\in\{0,1\}$.

Własność specjalna B: gwarantowane jest, że $p$ i $a$ są losowane spośród ciągów długości $n$ spełniających ograniczenia.

Uwaga: podzadania $3,4,5,8,9$ zależą od podzadania $2$.