Clownpiece is a fairy from Hell with the ability to increase the vitality of other fairies.

There are $n$ fairies in a row in the Sunflower Field. Each fairy has a vitality value, initially all $0$.

Clownpiece uses her ability to increase the vitality of the fairies. Specifically, she performs $m$ operations of two types:

• $1 \ x \ w$: Starting from the $x$-th fairy, increase the vitality of the $x$-th fairy by $w$; then, moving forward by $g_1$ fairies, increase the vitality of the $(x + g_1)$-th fairy by $w$; then, moving forward by $g_2$ fairies, increase the vitality of the $(x + g_1 + g_2)$-th fairy by $w$, and so on.
• $2 \ x$: Query the current vitality of the $x$-th fairy.

Here, $g$ is an infinitely long sequence defined as follows:

$$g_n = \begin{cases} 1 & n \equiv 1 \pmod 2 \\ 2 \times g_{n/2} & n \equiv 0 \pmod 2 \end{cases}$$

The first few terms of the sequence $g$ are: $[1, 2, 1, 4, 1, 2, 1, 8, 1, 2, \dots]$.

To prevent cheating, the operations are encrypted. See the Input section for details.

Input

The first line contains two integers $n, m$ ($1 \le n, m \le 3 \times 10^5$), representing the length of the fairy sequence and the total number of operations, respectively.

The next $m$ lines describe each operation:

• $1 \ x \ w$: Type 1 operation, where the actual $x = x \oplus \text{lastans}$, and the actual $w = w \oplus \text{lastans}$.
• $2 \ x$: Type 2 operation, where the actual $x = x \oplus \text{lastans}$.

Here, $\text{lastans}$ represents the result of the previous query. Specifically, initially $\text{lastans} = 0$.

The data guarantees that after decryption, $1 \le x \le n$ and $1 \le w \le 10^9$.

Output

Output several lines, one for each type 2 operation, containing the result.

Examples

Input 1

10 5
1 1 1
2 10
1 4 3
1 5 4
2 9

Output 1

1
7

Note

The decrypted input data is as follows:

10 5
1 1 1
2 10
1 5 2
1 4 5
2 8

• Initially, the sequence is $0, 0, 0, 0, 0, 0, 0, 0, 0, 0$.
• After the 1st operation, the sequence is $1, 1, 0, 1, 1, 0, 0, 0, 1, 1$.
• The 2nd operation queries the element at position $10$, which is $1$.
• After the 3rd operation, the sequence is $1, 1, 0, 1, 3, 2, 0, 2, 3, 1$.
• After the 4th operation, the sequence is $1, 1, 0, 6, 8, 2, 5, 7, 3, 1$.
• The 5th operation queries the element at position $8$, which is $7$.