You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

老年选手bibibibi比较擅长数据结构，于是YaoBIG准备了一个简单的数据结构题来让bibibibi解答。

给定一个长度为$n$的二进制数字，初始所有位置都是$0$，再给定$m$个操作，每个操作是下面三个操作的一种：

• $1$ $x$ 将第$x$位的数字取反（$1\le x\le n$）
• $2$ $x$ 回推到第$x$操作之后的状态（保证合法，即$0\le x\lt i$，其中$i$表示当前为第$i$次操作，$x$为$0$表示回到初始状态）
• $3$ $x$ 查询第$x$位置的数字并输出（$1\le x\le n$）

bibibibi由于太菜了做不出来，所以请求大家帮助解答YaoBIG的题目

Format

Input

第一行依次是两个正整数$n$和$m$，表示二进制数字长度$n$与操作数量$m$。

接下来$m$行每行两个整数$opt$和$x$，分别表示每次的操作类型以及操作数$x$。

Output

输出若干行，对每个操作$3$输出一行表示该次查询的结果。

Samples

5 10
1 4
3 4
1 3
3 3
1 2
3 1
2 0
3 4
2 2
3 4

1
1
0
0
1

Limitation

对于所有数据，$1\le n,m\le 10^5$