Предыстория

«Дитя моё, если я дам тебе богатство на три жизни, будешь учиться?»

Сегодня 玛德琳 и 坏德琳 подошли к волшебному автомату. В нём есть шарики четырёх цветов, каждый со своим назначением. Синий шарик — самый простой: отскочив от него, вы получаете возможность сделать один рывок. Розовый шарик — улучшенная версия: отскочив от него, вы получаете два рывка. Отскок от белого шарика не даёт рывков. После одного отскока на жёлтом шарике вырастают шипы, и впоследствии касаться его уже нельзя.

Уровень в этом автомате можно описать последовательностью цветов. 玛德琳 и 坏德琳 играли очень долго, но так и не прошли первый уровень. От отчаяния 玛德琳 расплакалась! Она решила воспользоваться программой для читов! Эта программа весьма необычна: она может менять только белые и жёлтые шарики и только на синие и розовые, причём позиция изменяемого шарика каждый раз заранее определена. Узнав об этом, 坏德琳 решила помешать 玛德琳 жульничать, поэтому взломала программу и получила право менять цвет жёлтых шариков. При этом 玛德琳 считает, что цепочка одинаковых шариков делает уровень проще. Простотой уровня она называет максимальную длину одноцветного отрезка. 玛德琳 хочет максимизировать эту величину, а 坏德琳 — минимизировать.

Условие задачи

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$ получается применением побитового исключающего ИЛИ к $A'_i$ и $ans_{i-1}$ и последующим взятием остатка по модулю $2$.

Выходные данные

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

Если $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$.