Передісторія

«Добра дитино, якби тобі дали багатство на три життя й три втілення, чи стала б ти вчитися?»

Сьогодні 玛德琳 і 坏德琳 підійшли до дивовижного автомата. Усередині нього є кулі чотирьох кольорів, кожна зі своїм призначенням. Синя пружна куля — найпростіша: відскочивши від неї, ви отримуєте можливість зробити один ривок. Рожева куля — покращена версія: відскочивши від неї, ви отримуєте два ривки. Відскок від білої кулі не дає ривків. Після першого відскоку жовта куля вкривається шипами, і надалі торкатися її вже не можна.

Рівень усередині автомата можна описати послідовністю кольорів. 玛德琳 і 坏德琳 грали там дуже довго, але так і не пройшли першого рівня. 玛德琳 аж розплакалася від розпачу! Вона вирішила зшахраювати за допомогою програми для модифікації гри! Ця програма особлива: вона може змінювати лише білі та жовті кулі, і лише на сині або рожеві, причому позиція кулі, яку змінюють на кожному кроці, визначена заздалегідь. Дізнавшись про це, 坏德琳 вирішила завадити 玛德琳 шахраювати, тому зламала програму й отримала право змінювати колір жовтих куль. Водночас 玛德琳 вважає, що довга низка однакових куль робить рівень простішим. Вона визначає простоту рівня як найбільшу довжину одноколірного відрізка. 玛德琳 хоче максимізувати це значення, а 坏德琳 — мінімізувати.

Опис задачі

Alice і Bob грають у гру на послідовності довжини $n$. Значення кожного елемента послідовності може дорівнювати лише $0$ або $1$, а момент визначення значення кожного елемента задано ще до початку гри.

Дано послідовності $p$ та $a$ довжини $n$, де $p$ — перестановка $1\dots n$, а $a_i\in\{-2,-1,0,1\}$.

Значення $i$-го елемента послідовності визначається в момент $p_i$ за такими правилами:

• Якщо $a_i=0$, цьому елементу присвоюється значення $0$;
• якщо $a_i=1$, цьому елементу присвоюється значення $1$;
• якщо $a_i=-1$, значення цього елемента в цей момент визначає Alice;
• якщо $a_i=-2$, значення цього елемента в цей момент визначає Bob.

До початку гри Alice і Bob знають обидві послідовності $p$ та $a$. Гра триває $n$ моментів часу. У момент $k$ визначається значення елемента на тій позиції $i$, для якої $p_i=k$; після завершення всіх $n$ моментів часу значення кожного елемента послідовності буде визначено рівно один раз.

Одноколірний неперервний відрізок визначається як пара $(l,r)$, для якої $l\le r$ і всі елементи від $l$-го до $r$-го мають однакове значення. Якщо його не можна продовжити ні ліворуч, ні праворуч (тобто $l=1$ або значення $l-1$-го елемента відрізняється від їхнього, і $r=n$ або значення $r+1$-го елемента відрізняється від їхнього), він називається максимальним за включенням одноколірним неперервним відрізком. Довжина $(l,r)$ дорівнює $r-l+1$.

Alice хоче максимізувати найбільшу довжину серед усіх максимальних за включенням одноколірних неперервних відрізків послідовності після моменту $n$, а Bob хоче мінімізувати це значення.

Дано додатне ціле число $typ \in \{1,2\}$.

Якщо $typ=1$, обидва гравці діятимуть оптимально. Знайдіть найбільшу довжину максимального за включенням одноколірного неперервного відрізка кінцевої послідовності. Можна довести, що відповідь визначена однозначно.

Якщо $typ=2$, додатково дано послідовність $A$ довжини $n$. Значення $A_i \in \{0,1\}$ означає таке рішення в момент $i$ гри: нехай $x$ — єдине додатне ціле число з-поміж $1,2,\dots,n$, для якого $p_x=i$; тоді $x$-му елементу послідовності присвоюється значення $A_i$ (можливо, космічний промінь влучить у позицію $x$, через що станеться випадок $a_x,A_i \in \{0,1\}$ та $a_x \neq A_i$). Для кожного $i=0,1,\dots,n$ знайдіть довжину $ans_i$ найдовшого одноколірного неперервного відрізка кінцевої послідовності, якщо до моменту $i$ включно гравці приймають рішення згідно з послідовністю $A$, а після завершення моменту $i$ обидва діють оптимально.

Вхідні дані

Цю задачу необхідно розв'язувати в онлайн-режимі.

Перший рядок містить додатне ціле число $T$ — кількість наборів даних.

Далі йдуть $T$ наборів даних. У кожному з них:

Перший рядок містить два додатні цілі числа $n$ та $typ$.

Другий рядок містить $n$ цілих чисел $p_1,p_2,\dots,p_n$.

Третій рядок містить $n$ цілих чисел $a_1,a_2,\dots,a_n$.

Якщо $typ=2$, четвертий рядок містить $n$ цілих чисел $A'_1,A'_2,\dots,A'_n$.

Справжнє значення $A_i$ дорівнює остачі від ділення на $2$ результату побітового виключного «або» чисел $A'_i$ та $ans_{i-1}$.

Вихідні дані

Для кожного набору даних:

Якщо $typ=1$, виведіть в одному рядку одне ціле число — довжину найдовшого одноколірного неперервного відрізка кінцевої послідовності, коли обидва гравці діють оптимально.

Якщо $typ=2$, виведіть в одному рядку $n+1$ цілих чисел: для кожного $i=0,1,\dots,n$ — довжину найдовшого одноколірного неперервного відрізка кінцевої послідовності, якщо до моменту $i$ включно гравці приймають рішення згідно з послідовністю $A$, а після завершення моменту $i$ обидва діють оптимально.

Приклади

Вхідні дані 1

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

Вихідні дані 1

3

Примітка

$p=[3,1,2]$ означає $p_1=3,\ p_2=1,\ p_3=2$: значення $1$-го елемента визначається в момент $3$, $2$-го — у момент $1$, а $3$-го — у момент $2$. Отже, порядок моментів часу такий:

• Момент $1$: визначається значення $2$-го елемента ($a_2=-2$, рішення приймає Bob);
• момент $2$: визначається значення $3$-го елемента ($a_3=-1$, рішення приймає Alice);
• момент $3$: визначається значення $1$-го елемента ($a_1=-1$, рішення приймає Alice).

Alice хоче, щоб найдовший одноколірний відрізок був якомога довшим, а Bob — якомога коротшим. Хоча Bob ходить першим, він контролює лише $2$-й елемент посередині; Alice контролює два крайні елементи — $1$-й та $3$-й.

Якщо Bob надасть $2$-му елементу значення $0$, Alice може також надати $1$-му та $3$-му елементам значення $0$, отримавши кінцеву послідовність 0 0 0 з найдовшим одноколірним відрізком довжини $3$. Якщо ж Bob надасть $2$-му елементу значення $1$, Alice так само вибере для обох значення $1$, отримавши кінцеву послідовність 1 1 1, у якій найдовший одноколірний відрізок знову має довжину $3$.

Обидва варіанти вибору Bob дають однаковий результат: він не може зменшити відповідь нижче $3$. Водночас Alice щонайбільше може зробити одноколірною всю послідовність, тому відповідь дорівнює $3$.

Вхідні дані 2

1
2 1
2 1
-1 -1

Вихідні дані 2

2

Примітка

$p=[2,1]$ означає $p_1=2,\ p_2=1$: значення $1$-го елемента визначається в момент $2$, а $2$-го — у момент $1$. Значення $a$ обох елементів дорівнюють $-1$, тому обидва визначає Alice:

• Момент $1$: визначається значення $2$-го елемента ($a_2=-1$, рішення приймає Alice);
• момент $2$: визначається значення $1$-го елемента ($a_1=-1$, рішення приймає Alice).

Alice хоче максимізувати довжину найдовшого одноколірного відрізка. Оскільки вона визначає обидва елементи, достатньо надати їм однакові значення, отримавши 0 0 або 1 1. Тоді $(1,2)$ — максимальний за включенням одноколірний неперервний відрізок довжини $2$. Загальна довжина послідовності дорівнює лише $2$, тож це найкращий результат, якого вона може досягти.

Вхідні дані 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

Вихідні дані 3

1
2 2 3 2 2
2

Обмеження

У цій задачі застосовуються відповідні залежності між підзадачами.

Для всіх наборів даних гарантовано:

• $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$ — перестановка $1\dots n$.

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

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

Особлива властивість A: гарантовано $a_i\in\{0,1\}$.

Особлива властивість B: гарантовано, що $p$ та $a$ генеруються випадково серед послідовностей довжини $n$, які задовольняють обмеження.

Увага: підзадачі $3,4,5,8,9$ залежать від підзадачі $2$.