Latar Belakang

“Anak baik, jika kuberikan kekayaan untuk tiga kehidupan, maukah kamu belajar?”

Hari ini, 玛德琳 dan 坏德琳 mendatangi sebuah mesin yang fantastis. Di dalam mesin tersebut terdapat bola dengan empat warna, masing-masing dengan kegunaannya sendiri. Bola biru adalah bola paling dasar: ketika kamu memantul darinya, kamu memperoleh kemampuan melakukan satu kali dash. Bola merah muda adalah versi yang lebih kuat: ketika kamu memantul darinya, kamu memperoleh dua kali dash. Memantul dari bola putih tidak memberikan dash. Setelah dipantuli sekali, bola kuning akan menumbuhkan duri, dan setelah itu kamu tidak boleh menyentuhnya lagi.

Level di dalamnya dapat dideskripsikan dengan sebuah urutan warna. 玛德琳 dan 坏德琳 sudah bermain di dalamnya cukup lama, tetapi belum berhasil melewati level pertama. 玛德琳 pun menangis karena frustrasi! Ia memutuskan untuk berbuat curang menggunakan alat pengubah! Alat ini sangat khusus: hanya bola putih dan kuning yang dapat diubah, dan hanya dapat diubah menjadi bola biru dan merah muda. Selain itu, posisi bola yang diubah pada setiap kesempatan sudah ditentukan. Ketika 坏德琳 mengetahui hal ini, ia memutuskan untuk menghentikan kecurangan 玛德琳, sehingga ia meretas alat tersebut dan memperoleh wewenang untuk mengubah warna bola kuning. Sementara itu, 玛德琳 menganggap bahwa deretan bola yang sama akan membuat sebuah level lebih mudah. Ia mendefinisikan tingkat kemudahan suatu level sebagai panjang maksimum segmen dengan warna yang sama. 玛德琳 ingin memaksimalkan nilai ini, sedangkan 坏德琳 ingin meminimalkannya.

Deskripsi Soal

Alice dan Bob memainkan sebuah permainan pada barisan dengan panjang $n$. Nilai setiap elemen barisan hanya dapat berupa $0$ atau $1$, dan waktu penentuan nilai setiap elemen sudah ditetapkan sebelum permainan dimulai.

Diberikan barisan $p$ dan $a$ dengan panjang $n$, dengan $p$ merupakan permutasi dari $1\dots n$, dan $a_i\in\{-2,-1,0,1\}$.

Nilai elemen ke-$i$ pada barisan ditentukan pada waktu ke-$p_i$, dengan aturan berikut:

• Jika $a_i=0$, elemen tersebut diberi nilai $0$;
• Jika $a_i=1$, elemen tersebut diberi nilai $1$;
• Jika $a_i=-1$, nilai elemen tersebut ditentukan oleh Alice pada waktu tersebut;
• Jika $a_i=-2$, nilai elemen tersebut ditentukan oleh Bob pada waktu tersebut.

Sebelum permainan dimulai, Alice dan Bob sama-sama mengetahui barisan $p$ dan barisan $a$. Permainan berlangsung selama $n$ langkah waktu. Pada waktu ke-$k$, nilai yang ditentukan adalah nilai pada posisi $i$ yang memenuhi $p_i=k$; setelah $n$ langkah waktu selesai, nilai setiap elemen barisan telah ditentukan tepat satu kali.

Segmen berurutan dengan warna yang sama didefinisikan sebagai pasangan $(l,r)$ yang memenuhi $l\le r$, dengan semua elemen dari elemen ke-$l$ sampai elemen ke-$r$ memiliki nilai yang sama. Jika segmen tersebut tidak dapat diperpanjang ke kiri maupun ke kanan (yaitu $l=1$ atau elemen ke-$l-1$ berbeda dari elemen-elemen tersebut, dan $r=n$ atau elemen ke-$r+1$ berbeda dari elemen-elemen tersebut), segmen itu disebut segmen berurutan sewarna yang maksimal. Panjang $(l,r)$ adalah $r-l+1$.

Alice ingin memaksimalkan panjang maksimum di antara semua segmen berurutan sewarna yang maksimal pada barisan setelah waktu ke-$n$, sedangkan Bob ingin meminimalkan nilai tersebut.

Diberikan bilangan bulat positif $typ \in \{1,2\}$.

Jika $typ=1$, kedua pemain bertindak dengan strategi optimal. Tentukan panjang maksimum segmen berurutan sewarna yang maksimal pada barisan akhir. Dapat dibuktikan bahwa jawabannya pasti.

Jika $typ=2$, diberikan pula barisan $A$ dengan panjang $n$. $A_i \in \{0,1\}$ menyatakan bahwa keputusan pada waktu ke-$i$ dalam permainan adalah sebagai berikut: misalkan $x$ adalah satu-satunya bilangan bulat positif di antara $1,2,\dots,n$ yang memenuhi $p_x=i$, maka elemen ke-$x$ pada barisan diberi nilai $A_i$ (sinar kosmik mungkin mengenai posisi ke-$x$, sehingga dapat terjadi $a_x,A_i \in \{0,1\}$ dan $a_x \neq A_i$). Untuk setiap $i=0,1,\dots,n$, tentukan panjang $ans_i$ dari segmen berurutan sewarna terpanjang pada barisan akhir apabila permainan mengikuti keputusan dalam barisan $A$ sampai dengan waktu ke-$i$, dan kedua pemain bertindak dengan strategi optimal setelah waktu ke-$i$ selesai.

Masukan

Soal ini mewajibkan pemrosesan secara online

Baris pertama berisi sebuah bilangan bulat positif $T$, yang menyatakan banyaknya kasus uji.

Selanjutnya terdapat $T$ kasus uji. Pada setiap kasus uji:

Baris pertama berisi dua bilangan bulat positif $n$ dan $typ$.

Baris kedua berisi $n$ bilangan bulat $p_1,p_2,\dots,p_n$.

Baris ketiga berisi $n$ bilangan bulat $a_1,a_2,\dots,a_n$.

Jika $typ=2$, baris keempat berisi $n$ bilangan bulat $A'_1,A'_2,\dots,A'_n$.

Nilai $A_i$ yang sebenarnya adalah hasil operasi XOR bitwise antara $A'_i$ dan $ans_{i-1}$, kemudian diambil modulo $2$.

Keluaran

Untuk setiap kasus uji:

Jika $typ=1$, keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan panjang segmen berurutan sewarna terpanjang pada barisan akhir ketika kedua pemain bertindak dengan strategi optimal.

Jika $typ=2$, keluarkan satu baris berisi $n+1$ bilangan bulat yang menyatakan, untuk setiap $i=0,1,\dots,n$, panjang segmen berurutan sewarna terpanjang pada barisan akhir apabila permainan mengikuti keputusan dalam barisan $A$ sampai dengan waktu ke-$i$, dan kedua pemain bertindak dengan strategi optimal setelah waktu ke-$i$ selesai.

Contoh

Masukan 1

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

Keluaran 1

3

Catatan

$p=[3,1,2]$ berarti $p_1=3,\ p_2=1,\ p_3=2$: elemen ke-$1$ ditentukan pada waktu ke-$3$, elemen ke-$2$ ditentukan pada waktu ke-$1$, dan elemen ke-$3$ ditentukan pada waktu ke-$2$. Jadi, urutan waktunya adalah:

• Waktu $1$: menentukan elemen ke-$2$ ($a_2=-2$, ditentukan oleh Bob);
• Waktu $2$: menentukan elemen ke-$3$ ($a_3=-1$, ditentukan oleh Alice);
• Waktu $3$: menentukan elemen ke-$1$ ($a_1=-1$, ditentukan oleh Alice).

Alice ingin agar segmen sewarna terpanjang menjadi sepanjang mungkin, sedangkan Bob ingin agar segmen tersebut sependek mungkin. Meskipun Bob mendapat giliran pertama, ia hanya mengendalikan elemen ke-$2$ yang berada tepat di tengah; Alice mengendalikan kedua elemen ujung, yaitu elemen ke-$1$ dan ke-$3$.

Setelah Bob menetapkan elemen ke-$2$ menjadi $0$, Alice dapat menetapkan elemen ke-$1$ dan ke-$3$ menjadi $0$ juga, sehingga barisan akhirnya adalah 0 0 0 dan panjang segmen sewarna terpanjangnya adalah $3$. Jika Bob menetapkan elemen ke-$2$ menjadi $1$, Alice juga memilih $1$ untuk keduanya, sehingga barisan akhirnya adalah 1 1 1 dan panjang segmen sewarna terpanjangnya tetap $3$.

Kedua pilihan Bob menghasilkan hasil yang sama persis, sehingga ia tidak dapat menekan jawaban menjadi kurang dari $3$. Sementara itu, paling jauh Alice hanya dapat membuat seluruh barisan memiliki warna yang sama, jadi jawabannya adalah $3$.

Masukan 2

1
2 1
2 1
-1 -1

Keluaran 2

2

Catatan

$p=[2,1]$ berarti $p_1=2,\ p_2=1$: elemen ke-$1$ ditentukan pada waktu ke-$2$, dan elemen ke-$2$ ditentukan pada waktu ke-$1$. Nilai $a$ kedua elemen adalah $-1$, sehingga keduanya ditentukan oleh Alice:

• Waktu $1$: menentukan elemen ke-$2$ ($a_2=-1$, ditentukan oleh Alice);
• Waktu $2$: menentukan elemen ke-$1$ ($a_1=-1$, ditentukan oleh Alice).

Alice ingin memaksimalkan panjang segmen sewarna terpanjang. Karena ia menentukan kedua elemen, ia cukup memberikan nilai yang sama kepada keduanya untuk mendapatkan 0 0 atau 1 1. Dalam hal ini, $(1,2)$ merupakan segmen berurutan sewarna yang maksimal dengan panjang $2$. Karena panjang seluruh barisan hanya $2$, ini juga merupakan hasil terbaik yang dapat ia capai.

Masukan 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

Keluaran 3

1
2 2 3 2 2
2

Batasan

Dependensi antarsubsoal yang sesuai diberlakukan pada soal ini.

Untuk semua data, dijamin bahwa:

• $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$ merupakan permutasi dari $1\dots n$.

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

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

Sifat Khusus A: Dijamin bahwa $a_i\in\{0,1\}$.

Sifat Khusus B: Dijamin bahwa $p$ dan $a$ dibangkitkan secara acak dari barisan dengan panjang $n$ yang memenuhi batasan.

Perhatikan: Subsoal $3,4,5,8,9$ bergantung pada subsoal $2$.