WWT 大爺是一位魔法師，最近他盯上了 OI 中的線段樹這個資料結構，並且正在對它進行改造。

在普通的線段樹當中，對於一個區間 $[l,r]$，我們會選擇 $mid= \lfloor \frac{l+r}{2} \rfloor$，將該區間分成 $[l,mid],[mid+1,r]$。它們在樹上則對應的節點是原區間對應節點的左右兒子。

魔法師 WWT 使用了高位魔法將此規則打破，在他的線段樹裡，他可以自己選擇 $mid$ 的值（但 $mid$ 依然滿足 $l \leq mid < r$），以至於使得線段樹的深度超過原來的限制 $O(\log n)$，以及區間定位時間複雜度超過原來的限制 $O(\log n)$。但其餘條件基本同原 OI 中的線段樹。

如下圖，是一棵 $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$ 行以先序遍歷（深度優先順序）描述一棵線段樹，每行一個正整數表示當前非葉子節點的 $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$ 的父親節點為軸進行一次旋轉操作，若 $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$。