题目描述

题目来源：CQOI 2006

有一个 \(n\) 个元素的数组，每个元素初始均为 \(0\)。有 \(m\) 条指令，要么让其中一段连续序列数字反转——\(0\) 变 \(1\)，\(1\) 变 \(0\)（操作 \(1\)），要么询问某个元素的值（操作 \(2\)）。

例如当 \(n=20\) 时，\(10\) 条指令如下：

操作	回答	操作后的数组
\(1\ 1\ 10\)	N/A	\(11111111110000000000\)
\(2\ 6\)	\(1\)	\(11111\underline{1}11110000000000\)
\(2\ 12\)	\(0\)	\(11111111110\underline{0}00000000\)
\(1\ 5\ 12\)	N/A	\(11110000001100000000\)
\(2\ 6\)	\(0\)	\(11110\underline{0}00001100000000\)
\(2\ 15\)	\(0\)	\(11110000001100\underline 000000\)
\(1\ 6\ 16\)	N/A	\( 11110111110011110000\)
\(1\ 11\ 17\)	N/A	\(11110111111100001000\)
\(2\ 12\)	\(1\)	\(11110111111\underline 100001000\)
\(2\ 6\)	\(1\)	\(11110\underline 111111100001000\)

输入格式

第一行包含两个整数 \(n,m\)，表示数组的长度和指令的条数；

以下 \(m\) 行，每行的第一个数 \(t\) 表示操作的种类：

+ 若 \(t=1\)，则接下来有两个数 \(L, R\)，表示区间 \([L, R]\) 的每个数均反转；
+ 若 \(t=2\)，则接下来只有一个数 \(i\)，表示询问的下标。

输出格式

每个操作 \(2\) 输出一行（非 \(0\) 即 \(1\)），表示每次操作 \(2\) 的回答。

样例数据

样例输入

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

限制与提示

对于 \(50\%\) 的数据，\(1\le n\le 10^3,1\le m\le 10^4\)；

对于 \(100\%\) 的数据，\(1\le n\le 10^5,1\le m\le 5\times 10^5\)，保证 \(L\le R\)。