There is a strange tree in Mr. mej's garden.

Every node in this tree has a positive integer label, and the node with label 1 is the root. All positive integers appear as labels in this tree. Furthermore, the node with label $i$ has exactly $i$ children, and the labels of these $i$ children are consecutive: let $mn(i)$ be the smallest label among the children of node $i$, and $mx(i)$ be the largest. Then $mx(i) - mn(i) = i - 1$, and all numbers in the range $mn(i) \sim mx(i)$ appear exactly once. Moreover, for any $1 \le i < j$, we have $mx(i) < mn(j)$.

It can be observed that these properties uniquely determine this strange tree. For example, the children of node 1 are $\{2\}$, the children of node 2 are $\{3, 4\}$, the children of node 3 are $\{5, 6, 7\}$, and so on. However, because Mr. mej does not like infinitely large trees, he only keeps the nodes with labels between $1 \sim n$ on this tree.

Mr. mej can obtain mana from this strange tree. Specifically, each node on the tree has a magic value, and initially, the magic value of all nodes is 0. He can choose a node $x$ to start obtaining mana, at which point he will obtain the XOR sum of the magic values of all nodes in the subtree of $x$ (including $x$). At the same time, he will maintain the tree: each time he chooses a node $x$ and a value $c$, he casts a spell to perform a bitwise OR operation on the magic values of all nodes in the subtree of $x$ with $c$.

Now, Mr. mej has performed $q$ operations in total, where each operation is either maintaining the strange tree or obtaining mana. He wants to know the amount of mana he obtains each time he performs the "obtain mana" operation.

Input

The input is read from standard input.

The first line contains two positive integers $n, q$ ($1 \le n \le 10^{18}, 1 \le q \le 10^6$), representing the size of the tree and the number of operations.

The next $q$ lines each start with a positive integer $op$ ($op \in \{1, 2\}$), representing the operation type. If $op = 1$, then two integers $x, c$ ($1 \le x \le n, 1 \le c < 2^{60}$) are provided, representing that the magic values of all nodes in the subtree rooted at $x$ are bitwise ORed with $c$. If $op = 2$, then a positive integer $x$ is provided, representing a query for the XOR sum of the magic values of all nodes in the subtree rooted at $x$.

Output

Output to standard output.

For each query, output an integer representing the required XOR sum.

Examples

Input 1

11 6
1 3 931
1 4 209
1 2 28
2 1
1 8 287
2 4

Output 1

193
479

Note

Initially, the magic values of all nodes are 0.

The first operation bitwise ORs the magic values of all nodes in the subtree rooted at 3 with 931. The sequence of magic values for all nodes becomes $0, 0, 931, 0, 931, 931, 931, 0, 0, 0, 0$.

The second operation bitwise ORs the magic values of all nodes in the subtree rooted at 4 with 209. The sequence of magic values becomes $0, 0, 931, 209, 931, 931, 931, 209, 209, 209, 209$.

The third operation bitwise ORs the magic values of all nodes in the subtree rooted at 2 with 28. The sequence of magic values becomes $0, 28, 959, 221, 959, 959, 959, 221, 221, 221, 221$.

The fourth operation queries the XOR sum of the magic values of all nodes in the subtree rooted at 1, which is $0 \oplus 28 \oplus 959 \oplus 221 \oplus 959 \oplus 959 \oplus 959 \oplus 221 \oplus 221 \oplus 221 \oplus 221 = 193$.

The fifth operation bitwise ORs the magic values of all nodes in the subtree rooted at 8 with 287. The sequence of magic values becomes $0, 28, 959, 221, 959, 959, 959, 479, 221, 221, 221$.

The sixth operation queries the XOR sum of the magic values of all nodes in the subtree rooted at 4, which is $221 \oplus 479 \oplus 221 \oplus 221 \oplus 221 = 479$.