Description

Source: CQOI 2006

There is an array of $n$ elements, each initially set to $0$. There are $m$ instructions, each either flipping a continuous segment of numbers—changing $0$ to $1$ and $1$ to $0$ (Operation $1$), or querying the value of a specific element (Operation $2$).

For example, when $n=20$, the $10$ instructions are as follows:

Input Format

The first line contains two integers $n$ and $m$, representing the length of the array and the number of instructions, respectively.
The following $m$ lines each start with an integer $t$ indicating the type of operation:

• If $t=1$, it is followed by two integers $L$ and $R$, indicating that each number in the interval $[L, R]$ should be flipped;
• If $t=2$, it is followed by a single integer $i$, representing the index to be queried.

Output Format

For each Operation $2$, output a line (either $0$ or $1$), representing the answer to the query.

Sample 1

20 10
1 1 10
2 6
2 12
1 5 12
2 6
2 15
1 6 16
1 11 17
2 12
2 6

1
0
0
0
1
1

Constraints & Hints

For $50\%$ of the data, $1\le n\le 10^3,1\le m\le 10^4$;
For $100\%$ of the data, $1\le n\le 10^5,1\le m\le 5\times 10^5$, with $L\le R$ guaranteed.