Problem Description

There is an array with $n$ elements, and each element is initially $0$. There are $m$ instructions, and each instruction is one of the following two operations:

1. Flip all numbers in a continuous segment. (That is, $0$ becomes $1$, and $1$ becomes $0$.)
2. Query the value of a certain element.

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

Input Format

The first line contains two integers $n, m$, representing the length of the array and the number of instructions.

In the next $m$ lines, the first number is $t$, representing the type of operation:

• If $t = 1$, then two numbers $L, R$ follow, meaning to flip every number in the interval $[L, R]$.
• If $t = 2$, then only one number $i$ follows, meaning to query the index.

Output Format

For each operation $2$, output one line (either $0$ or $1$), representing the answer to that query.

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

Hint

For $50\%$ of the testdata, $1 \le n \le 10^3$, $1 \le m \le 10^4$.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 5 \times 10^5$, and it is guaranteed that $L \le R$.

Translated by ChatGPT 5