Master WWT is a magician who has recently set his sights on the segment tree data structure in informatics, and he is currently in the process of modifying it.

In a standard segment tree, for an interval $[l, r]$, we choose $mid = \lfloor \frac{l+r}{2} \rfloor$ and split the interval into $[l, mid]$ and $[mid+1, r]$. These correspond to the left and right children of the node representing the original interval in the tree.

Magician WWT has used high-level magic to break this rule. In his segment tree, he can choose the value of $mid$ himself (provided that $l \leq mid < r$), which can cause the depth of the segment tree to exceed the original $O(\log n)$ limit, and the time complexity of interval decomposition to exceed the original $O(\log n)$ limit. However, all other conditions remain essentially the same as in a standard segment tree.

As shown in the figure below, this is a segment tree with arbitrary $mid$ values:

    *What is interval decomposition:
    Using the minimum number of segments represented by nodes in the segment tree to fit the interval, such that each unit length appears exactly once among these segments.
    For the segment tree above, the interval decomposition of [2,5] is [2,3], [4,4], [5,5], totaling three segments.
    It is not difficult to prove that such an interval decomposition is unique.

Magician WWT not only used high-level magic to break the fundamental laws of segment trees, but also used some forbidden magic to modify the structure of this segment tree. He performs left rotation or right rotation operations on specified sub-structures within the tree. As shown in the figure below:

    It is not difficult to see that this rotation rule is similar to the rotation pattern of a Splay tree.
    ① Subtrees A, B, and C do not undergo any changes.
    ② The relative positions between subtrees A, B, C and nodes X, Y will change.
    ③ The interval ranges of nodes X and Y will change.

Magician WWT will give you a segment tree with arbitrary $mid$ values. While performing rotations on certain nodes of this tree, he will ask you for the number of interval decomposition segments for a given interval on the current segment tree.

WWT felt that such a problem was not enough to demonstrate his superb magical level, so he encrypted some of the data, forcing participants' algorithms to be online.

Input

The first line contains three integers $N, Q, type$, representing the width of the segment tree, the number of operations, and whether the data is encrypted, respectively. If $type=0$, the data is not encrypted; if $type=1$, the data is encrypted.

The next $N-1$ lines describe a segment tree in pre-order traversal (depth-first order). Each line contains a positive integer representing the $mid$ of the current non-leaf node, ensuring that for every node $l \leq mid < r$. At the same time, we label all non-leaf nodes according to their pre-order traversal, from $1$ to $N-1$.

    When reading, it is recommended that participants use recursion directly and backtrack when reaching leaf nodes, so there are a total of N-1 mid values, and it is guaranteed that each number from 1 to N-1 appears exactly once.

Following this are $Q$ lines, each representing an operation.

The first integer $tp$ of each line represents the type of operation:

If $tp=0$, it represents a modification operation. The line also includes a positive integer $x'$. Let $lastans$ be the answer to the previous query; if there was no previous query, $lastans=0$. We define $x = x' \oplus (type \times lastans)$. $x$ represents the node index of the child node for the rotation operation. You need to perform a rotation operation using $x$ and its parent node as the axis. If $x$ is the left child of its parent, perform a right rotation; if $x$ is the right child of its parent, perform a left rotation. WWT is too confident in his magic, so sometimes the non-leaf node $x$ he provides is the index of the current root of the segment tree. This is an illegal modification operation; in this case, you need to output a line "BAD!" and perform no operations on the current segment tree.

If $tp=1$, it represents a query operation. The line also includes two positive integers $l', r'$. Let $lastans$ be the answer to the previous query; if there was no previous query, $lastans=0$. We define $l = l' \oplus (type \times lastans)$ and $r = r' \oplus (type \times lastans)$. Then $[l, r]$ represents the query interval. For each query, you need to provide the number of interval decomposition segments for this interval on the current segment tree.

Output

The output consists of several lines: For an illegal modification operation, output a line "BAD!"; For a query operation, output a positive integer representing the answer.

    No output is required for a legal modification operation.

Examples

Input 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

Output 1

4
3
4
4
2
3
4
1
3
BAD!

Note

The sample after decryption:

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

The initial shape of the segment tree is as follows:

1: The interval decomposition of $[3,6]$ is $[3,3],[4,4],[5,5],[6,6]$, totaling 4 segments.

2: The interval decomposition of $[2,7]$ is $[2,3],[4,4],[5,7]$, totaling 3 segments.

3: The interval decomposition of $[2,6]$ is $[2,3],[4,4],[5,5],[6,6]$, totaling 4 segments.

4: Perform a right rotation with 3 and its parent 2 as the axis. The shape after rotation is as follows:

5: The interval decomposition of $[3,6]$ is $[3,3],[4,4],[5,5],[6,6]$, totaling 4 segments.

6: The interval decomposition of $[2,7]$ is $[2,4],[5,7]$, totaling 2 segments.

7: The interval decomposition of $[2,6]$ is $[2,4],[5,5],[6,6]$, totaling 3 segments.

8: Perform a right rotation with 3 and its parent 1 as the axis. The shape after rotation is as follows:

9: The interval decomposition of $[3,6]$ is $[3,3],[4,4],[5,5],[6,6]$, totaling 4 segments.

10: The interval decomposition of $[2,7]$ is $[2,4],[5,7]$, totaling 2 segments.

11: The interval decomposition of $[2,6]$ is $[2,4],[5,5],[6,6]$, totaling 3 segments.

12: Node 3 is already the current root, an illegal modification operation, output "BAD!".

Constraints

For all data, the decrypted $l, r, x$ satisfy $1 \leq l \leq r \leq N$ and $1 \leq x \leq N-1$.