题目描述

几个月前，Kyusho 参加了远方城市 Overton 的一次颁奖典礼。

在比赛中，每位参赛者都有一个写着唯一编号的胸牌。颁奖过程非常混乱：不断有人登上舞台或离开舞台，也会在随机时刻给一段连续的参赛者颁发证书。

Kyusho 想知道：有多少离开舞台的人至少获得过一张证书。为描述这个过程，他把事件分成三类：

1. 当前站在最左边或最右边的参赛者离开舞台。
2. 给当前舞台上从编号为 $x$ 的参赛者到编号为 $y$ 的参赛者之间的所有人颁发证书，包括 $x$ 与 $y$ 本人。保证 $x$ 与 $y$ 当前都在舞台上，并且 $x$ 位于 $y$ 的左侧。若数据中出现 $x=y$，表示只给该参赛者颁发证书。
3. 编号为 $z$ 的参赛者登上舞台，并站在编号为 $x$ 与 $y$ 的两名参赛者之间。保证此前 $z$ 从未登上过舞台，并且当前 $x$ 与 $y$ 相邻。

请你处理所有事件。对于每个第 1 类事件，判断离开舞台的参赛者是否至少获得过一张证书。

输入格式

第一行包含两个整数 $N,Q$，分别表示初始在舞台上的参赛者数量和事件数量。

第二行包含 $N$ 个整数，表示初始时参赛者从左到右的编号。

接下来 $Q$ 行，每行描述一个事件：

• 若事件类型 $t=1$，则随后输入一个整数 $p$：
  • $p=1$ 表示最左边的参赛者离开；
  • $p=2$ 表示最右边的参赛者离开。
• 若事件类型 $t=2$，则随后输入两个整数 $x,y$，表示给从 $x$ 到 $y$ 这一段参赛者颁发证书。
• 若事件类型 $t=3$，则随后输入三个整数 $x,y,z$，表示参赛者 $z$ 站到相邻的 $x$ 与 $y$ 之间。

输出格式

输出一行一个由 0 和 1 组成的字符串，依次表示所有第 1 类事件的答案。

若对应离开的参赛者至少获得过一张证书，则输出 1，否则输出 0。

样例

5 9
3 5 2 1 6
2 5 1
3 5 2 4
3 1 6 7
1 1
1 1
2 2 7
1 2
1 2
1 1

01010

样例解释

初始队列为：

3 5 2 1 6

第一次颁奖给编号 $5,2,1$ 的参赛者。

之后 $4$ 插入到 $5$ 与 $2$ 之间，$7$ 插入到 $1$ 与 $6$ 之间，队列变为：

3 5 4 2 1 7 6

随后离场事件依次为：

• $3$ 离开，未获奖，输出 0；
• $5$ 离开，已获奖，输出 1；
• 第二次颁奖给从 $2$ 到 $7$ 的一段参赛者；
• $6$ 离开，未获奖，输出 0；
• $7$ 离开，已获奖，输出 1；
• $4$ 离开，未获奖，输出 0。

因此输出为 01010。

数据范围

• $2 \le N,Q \le 10^5$
• $1 \le x,y,z \le 3 \cdot 10^5$
• 保证任意时刻舞台上至少有两名参赛者。

子任务

只有通过一个子任务内的全部测试，才能获得该子任务分数。