Description

Yuki has a full binary tree with $n$ levels. The nodes are numbered according to a level-order traversal (see explanation).

This tree undergoes $m$ operations.

1. The tree experiences a fault. The edge between node $u$ and its parent is deleted. If the node is the root or this edge has already been deleted, nothing happens.

2. Query the size of the connected component containing node $u$.

Input Format

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain two integers $o$ and $u$.

If $o=1$, perform operation 1 on $u$. If $o=2$, perform operation 2 on $u$.

Output Format

To simplify the output, you only need to print one line, representing the XOR of all answers for each query.

5 3
2 3
1 3
2 3

16

5 3
1 2
1 3
2 1

1

Hint

Binary Tree and Related Issues

1. A full binary tree with $n$ levels refers to a full binary tree with a maximum depth of $n$, where the root node has a depth of 1.
2. If node $i$ has children, the level-order traversal numbering of the full binary tree satisfies that the left child of $i$ is $2i$ and the right child is $2i+1$.

Explanation for Sample 1

For the first query, before deleting the edge between 3 and 1, the answer is the size of the entire tree, which is 31. After deletion, it becomes the size of 3's subtree, which is 15. The XOR sum is $31\oplus 15=16$.

Data Range

There are 10 test cases.

For the first 20% of the data, $n \leq 10, m \leq 10^3$.

For the first 50% of the data, $n \leq 20, m \leq 10^4$.

For the first 80% of the data, $n \leq 30$.

For all data, $2 \leq n \leq 60, 1 \leq m \leq 3 \times 10^5, 1 \leq o \leq 2, 1 \leq u \leq 2^n -1$.