U561776 [WPXCO 1.2 MAY] Sphere

本题搬自 [WPXOJ](http://www.xn--4gvz61aoo7a.xn--fiqs8s )

Kirole 有一个数值编辑器，里面有 $n$ 个分页，第 $i$ 个分页内初始状态下只有一个数，为 $i$。 Kirole 会对它进行 $m$ 次操作。分为 $3$ 种： - `append a b` 合并 $a,b$ 所在分页； - `withdraw k` 回到第 $k$ 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态； - `belong a b` 询问 $a,b$ 是否属于同一分页，如果是则输出 $1$，否则输出 $0$。

第一行两个整数 $n, m$。 接下来 $m$ 行，每行先输入一个字符串 $opt$ 表示操作类型。若 $opt=\text{withdraw}$ 则输入一个整数 $k$，否则输入两个整数 $a,b$，描述一次操作。

对每个操作 $3$，输出一行一个整数表示答案。

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le m\le 2\times 10^5$，$1 \le a, b, k \le n$。