Маг WWT — волшебник, который недавно заинтересовался структурой данных «дерево отрезков» и решил её усовершенствовать.

В обычном дереве отрезков для интервала $[l, r]$ мы выбираем $mid = \lfloor \frac{l+r}{2} \rfloor$ и разбиваем интервал на $[l, mid]$ и $[mid+1, r]$. В дереве эти интервалы соответствуют левому и правому потомкам узла, представляющего исходный интервал.

Маг WWT использовал магию высокого уровня, чтобы нарушить это правило. В его дереве отрезков он может сам выбирать значение $mid$ (при условии $l \leq mid < r$), что может привести к тому, что глубина дерева превысит стандартное ограничение $O(\log n)$, а временная сложность позиционирования отрезка превысит стандартное $O(\log n)$. В остальном условия соответствуют обычному дереву отрезков.

На рисунке ниже показано дерево отрезков с произвольными значениями $mid$:

    *Что такое позиционирование отрезка:
    Это представление интервала с помощью минимального набора узлов дерева отрезков таких, что каждая единица длины интервала покрывается ровно один раз.
    Например, для дерева выше позиционирование отрезка [2,5] состоит из [2,3], [4,4], [5,5] — всего три сегмента.
    Нетрудно доказать, что такое позиционирование единственно.

Маг WWT не только нарушил фундаментальные принципы дерева отрезков, но и применил запретную магию, чтобы изменить структуру дерева. Он может выполнять операции левого или правого поворота для определённых подструктур дерева. Как показано на рисунке ниже:

    Нетрудно заметить, что правила поворота аналогичны поворотам в Splay-дереве.
    ① Поддеревья A, B, C не меняются.
    ② Относительное расположение поддеревьев A, B, C и узлов X, Y меняется.
    ③ Интервалы, соответствующие узлам X и Y, меняются.

Маг WWT даёт вам дерево отрезков с произвольными значениями $mid$. Вам необходимо выполнять повороты некоторых узлов и отвечать на запросы о количестве сегментов при позиционировании отрезка для заданного интервала в текущем дереве.

WWT посчитал, что эта задача недостаточно демонстрирует его магическое мастерство, поэтому он зашифровал некоторые данные, вынуждая участников решать задачу в режиме онлайн.

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

Первая строка содержит три целых числа $N, Q, type$, представляющие ширину дерева отрезков, количество операций и признак шифрования данных соответственно. Если $type=0$, данные не зашифрованы; если $type=1$, данные зашифрованы.

Следующие $N-1$ строк описывают дерево отрезков в порядке прямого обхода (DFS). Каждая строка содержит положительное целое число — значение $mid$ для текущего нелистового узла. Гарантируется, что для каждого узла $l \leq mid < r$. Все нелистовые узлы пронумерованы от $1$ до $N-1$ в порядке их появления при прямом обходе.

    При чтении рекомендуется использовать рекурсию: при достижении листового узла выполнять возврат. Всего будет N-1 значений mid, каждое число от 1 до N-1 встречается ровно один раз.

Далее следуют $Q$ строк, каждая из которых описывает операцию.

Первое число в строке $tp$ определяет тип операции:

Если $tp=0$, это операция модификации. Строка также содержит положительное целое число $x'$. Пусть $lastans$ — ответ на последний запрос (если запросов ещё не было, $lastans=0$). Определим $x = x' \oplus (type \times lastans)$. $x$ — это номер узла-потомка, вокруг которого и его родителя нужно выполнить поворот. Если $x$ является левым сыном своего родителя, выполняется правый поворот; если $x$ — правый сын, выполняется левый поворот. WWT слишком уверен в своей магии, поэтому иногда он может передать номер $x$, являющийся корнем текущего дерева. Это недопустимая операция: в таком случае выведите "BAD!" и не меняйте дерево.

Если $tp=1$, это операция запроса. Строка также содержит два положительных целых числа $l', r'$. Пусть $lastans$ — ответ на последний запрос (если запросов ещё не было, $lastans=0$). Определим $l = l' \oplus (type \times lastans)$ и $r = r' \oplus (type \times lastans)$. $[l, r]$ — это интервал запроса. Для каждого запроса выведите количество сегментов в позиционировании отрезка для данного интервала в текущем дереве.

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

Выходные данные должны содержать несколько строк: Для недопустимой операции модификации выведите "BAD!". Для операции запроса выведите положительное целое число — ответ.

    Для допустимых операций модификации вывод не требуется.

Примеры

Пример 1

7 12 1
4
3
1
2
5
6
1 3 6
1 6 3
1 1 5
0 7
1 7 2
1 6 3
1 0 4
0 0
1 0 5
1 6 3
1 3 7
0 0

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

4
3
4
4
2
3
4
1
3
BAD!

Примечание

После расшифровки примера:

7 12 0
4
3
1
2
5
6
1 3 6
1 2 7
1 2 6
0 3
1 3 6
1 2 7
1 2 6
0 3
1 3 6
1 2 7
1 2 6
0 3

Начальная форма дерева отрезков:

$1: [3, 6]$ позиционируется как $[3,3], [4,4], [5,5], [6,6]$, итого $4$.

$2: [2, 7]$ позиционируется как $[2,3], [4,4], [5,7]$, итого $3$.

$3: [2, 6]$ позиционируется как $[2,3], [4,4], [5,5], [6,6]$, итого $4$.

$4:$ Поворот вправо вокруг узла $3$ и его родителя $2$. Форма после поворота:

$5: [3, 6]$ позиционируется как $[3,3], [4,4], [5,5], [6,6]$, итого $4$.

$6: [2, 7]$ позиционируется как $[2,4], [5,7]$, итого $2$.

$7: [2, 6]$ позиционируется как $[2,4], [5,5], [6,6]$, итого $3$.

$8:$ Поворот вправо вокруг узла $3$ и его родителя $1$. Форма после поворота:

$9: [3, 6]$ позиционируется как $[3,3], [4,4], [5,5], [6,6]$, итого $4$.

$10: [2, 7]$ позиционируется как $[2,4], [5,7]$, итого $2$.

$11: [2, 6]$ позиционируется как $[2,4], [5,5], [6,6]$, итого $3$.

$12:$ Узел $3$ уже является корнем, недопустимая операция, вывод "BAD!".

Ограничения

Для всех данных после расшифровки $l, r, x$ удовлетворяют условиям $1 \leq l \leq r \leq N, 1 \leq x \leq N-1$.