魔法師 WWT は魔法使いであり、最近彼は OI におけるセグメント木というデータ構造に目をつけ、それを改造しようとしています。

通常のセグメント木において、ある区間 $[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)$ を超える可能性があります。しかし、その他の条件は通常の OI におけるセグメント木とほぼ同じです。

下図は、$mid$ が任意であるセグメント木の一例です。

*区間定位とは：
セグメント木上のノードで表される最小限の線分を用いてその区間を近似し、各単位長さがこれらの線分の中にちょうど一度だけ現れるようにすること。
上のセグメント木の例では、線分 [2,5] の区間定位は [2,3], [4,4], [5,5] の計3つである。
このような区間定位が一意であることは容易に証明できる。

魔法師 WWT は高位魔法を使ってセグメント木の基本原則を打ち破っただけでなく、禁忌の魔法を使ってこのセグメント木の構造を修正しました。彼は指定された木の中の特定のサブ構造に対して左回転または右回転の操作を行います。下図の通りです。

この回転規則は Splay 木の回転パターンと類似していることがわかる。
① 部分木 A, B, C は変化しない。
② 部分木 A, B, C およびノード X, Y の相対的な位置関係が変化する。
③ ノード X, Y の区間スケールが変化する。

魔法師 WWT はあなたに $mid$ 値が任意であるセグメント木を与えます。この木の特定のノードに対して回転操作を行うと同時に、ある区間が現在のセグメント木上で区間定位される個数を問い合わせます。

WWT はこれだけでは彼の高度な魔法のレベルを十分に示せないと考え、さらに一部のデータに対して暗号化を施し、参加者のアルゴリズムを強制オンラインにしました。

入力

第一行には3つの整数 $N, Q, type$ が含まれており、それぞれセグメント木の幅、操作回数、およびデータが暗号化されているかどうかを表します。$type=0$ の場合はデータが暗号化されていないことを示し、$type=1$ の場合はデータが暗号化されていることを示します。

続く $N-1$ 行は、先行順走査（深さ優先探索順）でセグメント木を記述します。各行の正整数は現在の非葉ノードの $mid$ を表し、各ノードで $l \leq mid < r$ であることが保証されます。また、すべての非葉ノードを先行順走査の順に $1$ から $N-1$ まで番号付けします。

読み込みの際は再帰を用いることを推奨する。葉ノードに到達した際にバックトラックすればよく、合計 N-1 個の mid があり、1 から N-1 までがそれぞれ一度ずつ現れることが保証されている。

その後、$Q$ 行の各行が1つの操作を表します。

各行の最初の整数 $tp$ は操作のタイプを表します。

$tp=0$ の場合、これは更新操作です。この行にはさらに正整数 $x'$ が含まれます。$lastans$ を前回の問い合わせの答えとします（以前に問い合わせ操作がない場合は $lastans=0$）。$x = x' \oplus (type \times lastans)$ と定義します。$x$ は回転操作を行う対象のノード番号を表します。$x$ とその親ノードを軸として回転操作を行ってください。$x$ が親の左の子であれば右回転を行い、$x$ が親の右の子であれば左回転を行います。WWT は自分の魔法に自信過剰であり、時として与えられる非葉ノード $x$ が現在のセグメント木の根の番号である場合があります。これは不正な更新操作であり、その場合は "BAD!" と一行出力し、現在のセグメント木に対して何の操作も行わないでください。

$tp=1$ の場合、これは問い合わせ操作です。この行にはさらに2つの正整数 $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$ を満たします。