WWT to magik, który niedawno zainteresował się strukturą danych, jaką jest drzewo przedziałowe (segment tree), i zaczął ją modyfikować.

W standardowym drzewie przedziałowym dla przedziału $[l, r]$ wybieramy $mid = \lfloor \frac{l+r}{2} \rfloor$ i dzielimy przedział na $[l, mid]$ oraz $[mid+1, r]$. W drzewie odpowiada to lewemu i prawemu synowi węzła reprezentującego dany przedział.

Magik WWT użył magii wysokiego poziomu, aby złamać tę zasadę. W jego drzewie przedziałowym może on samodzielnie wybierać wartość $mid$ (przy zachowaniu warunku $l \leq mid < r$), co sprawia, że głębokość drzewa może przekroczyć standardowe ograniczenie $O(\log n)$, a złożoność czasowa lokalizacji przedziału może przekroczyć standardowe $O(\log n)$. Pozostałe warunki są zasadniczo takie same jak w standardowym drzewie przedziałowym.

Poniższy rysunek przedstawia drzewo przedziałowe z dowolnie wybranymi wartościami $mid$:

Czym jest lokalizacja przedziału:
Użycie minimalnej liczby przedziałów reprezentowanych przez węzły drzewa, aby pokryć dany przedział, tak aby każda jednostka długości wystąpiła dokładnie raz.
Na przykład w powyższym drzewie, lokalizacja przedziału [2,5] to [2,3], [4,4], [5,5], łącznie trzy.
Łatwo dowieść, że taka lokalizacja przedziału jest unikalna.

Magik WWT nie tylko złamał podstawowe zasady drzewa przedziałowego, ale użył również zakazanej magii, aby zmodyfikować strukturę drzewa. Wykonuje on operacje rotacji w lewo lub rotacji w prawo na wybranych podstrukturach drzewa. Jak pokazano poniżej:

Łatwo zauważyć, że ta zasada rotacji jest podobna do rotacji w strukturze Splay.
① Poddrzewa A, B, C nie ulegają żadnym zmianom.
② Względne położenie poddrzew A, B, C oraz węzłów X, Y ulega zmianie.
③ Zakresy przedziałów węzłów X, Y ulegają zmianie.

Magik WWT poda Ci drzewo przedziałowe z dowolnymi wartościami $mid$. Podczas wykonywania rotacji na niektórych węzłach drzewa, będziesz musiał odpowiadać na zapytania o liczbę elementów w lokalizacji przedziału dla danego przedziału w aktualnym drzewie.

WWT uznał, że takie zadanie nie w pełni oddaje jego wysoki poziom magii, więc dodatkowo zaszyfrował niektóre dane, wymuszając na zawodnikach rozwiązanie typu online.

Wejście

Pierwsza linia zawiera trzy liczby całkowite $N, Q, type$, oznaczające odpowiednio szerokość drzewa przedziałowego, liczbę operacji oraz informację, czy dane są zaszyfrowane. Jeśli $type=0$, dane nie są zaszyfrowane; jeśli $type=1$, dane są zaszyfrowane.

Kolejne $N-1$ linii opisuje drzewo przedziałowe w porządku pre-order (przeszukiwanie w głąb). Każda linia zawiera jedną liczbę całkowitą oznaczającą $mid$ bieżącego węzła wewnętrznego. Gwarantuje się, że dla każdego węzła $l \leq mid < r$. Ponadto, numerujemy wszystkie węzły wewnętrzne zgodnie z kolejnością ich występowania w pre-order, od $1$ do $N-1$.

Podczas wczytywania zaleca się użycie rekurencji i powrót (backtracking) po dotarciu do liścia. Łącznie jest N-1 wartości mid, przy czym każda liczba od 1 do N-1 występuje dokładnie raz.

Następnie następuje $Q$ linii, z których każda reprezentuje operację.

Pierwsza liczba w linii $tp$ oznacza typ operacji:

Jeśli $tp=0$, jest to operacja modyfikacji. Linia zawiera również liczbę całkowitą $x'$. Niech $lastans$ będzie odpowiedzią na ostatnie zapytanie (jeśli wcześniej nie było zapytań, $lastans=0$). Definiujemy $x = x' \oplus (type \times lastans)$. $x$ oznacza numer węzła-syna dla operacji rotacji. Należy wykonać rotację wokół osi utworzonej przez $x$ i jego ojca. Jeśli $x$ jest lewym synem swojego ojca, wykonaj rotację w prawo; jeśli $x$ jest prawym synem, wykonaj rotację w lewo. WWT jest zbyt pewny swojej magii, więc czasami podaje jako $x$ numer korzenia aktualnego drzewa przedziałowego. Jest to niepoprawna operacja modyfikacji; w takim przypadku należy wypisać "BAD!" i nie wykonywać żadnych operacji na drzewie.

Jeśli $tp=1$, jest to operacja zapytania. Linia zawiera również dwie liczby całkowite $l', r'$. Niech $lastans$ będzie odpowiedzią na ostatnie zapytanie (jeśli wcześniej nie było zapytań, $lastans=0$). Definiujemy $l = l' \oplus (type \times lastans)$ oraz $r = r' \oplus (type \times lastans)$. $[l, r]$ oznacza przedział zapytania. Dla każdego zapytania należy podać liczbę elementów w lokalizacji przedziału dla tego przedziału w aktualnym drzewie.

Wyjście

Wyjście powinno zawierać odpowiednią liczbę linii: Dla niepoprawnej operacji modyfikacji wypisz "BAD!". Dla operacji zapytania wypisz liczbę całkowitą będącą odpowiedzią.

Dla poprawnej operacji modyfikacji nie należy nic wypisywać.

Przykład

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

Wyjście 1

4
3
4
4
2
3
4
1
3
BAD!

Uwagi

Po odszyfrowaniu przykładu:

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

Początkowy kształt drzewa przedziałowego:

$1: [3,6]$ lokalizacja przedziału to $[3,3],[4,4],[5,5],[6,6]$, łącznie $4$.

$2: [2,7]$ lokalizacja przedziału to $[2,3],[4,4],[5,7]$, łącznie $3$.

$3: [2,6]$ lokalizacja przedziału to $[2,3],[4,4],[5,5],[6,6]$, łącznie $4$.

$4:$ Rotacja w prawo wokół węzła $3$ i jego ojca $2$. Kształt po rotacji:

$5: [3,6]$ lokalizacja przedziału to $[3,3],[4,4],[5,5],[6,6]$, łącznie $4$.

$6: [2,7]$ lokalizacja przedziału to $[2,4],[5,7]$, łącznie $2$.

$7: [2,6]$ lokalizacja przedziału to $[2,4],[5,5],[6,6]$, łącznie $3$.

$8:$ Rotacja w prawo wokół węzła $3$ i jego ojca $1$. Kształt po rotacji:

$9: [3,6]$ lokalizacja przedziału to $[3,3],[4,4],[5,5],[6,6]$, łącznie $4$.

$10: [2,7]$ lokalizacja przedziału to $[2,4],[5,7]$, łącznie $2$.

$11: [2,6]$ lokalizacja przedziału to $[2,4],[5,5],[6,6]$, łącznie $3$.

$12:$ Węzeł $3$ jest już korzeniem, niepoprawna operacja modyfikacji, wypisz "BAD!".

Ograniczenia

Dla wszystkich danych, po odszyfrowaniu $l, r, x$ spełniają $1 \leq l \leq r \leq N, 1 \leq x \leq N-1$.