题目描述

管理员指挥一批机器人站成一排。可以把它们看作站在一条数轴上，每个机器人所在的位置就是数轴上对应的数字。管理员会告知你，第 $i$ 个机器人的初始位置为 $a_i$。不保证 $\bm{a_i}$ 是按从小到大顺序排列的。

数轴的范围是有限定的，具体范围为 $[-s,s]$。也就是说，要是某个机器人移动到了这个范围之外，就会脱离队列，并且不会再回到队列中。

为了训练机器人，管理员下达了 $t$ 个指令，指令分为以下 3 种：

• 指令 1：所有机器人向数轴的正方向移动 $d$ 个单位长度。

• 指令 2：所有机器人向数轴的反方向移动 $d$ 个单位长度。

• 指令 3：依次清点，统计当前队列中机器人的总数。

然而，管理员发现机器人的数量实在太多，导致执行这些操作时速度很慢。不过，管理员还是希望你能告诉他所有指令 3 的执行结果。

输入格式

第一行有 3 个整数 $p, t, s$，含义如题面所述。

第二行有 $p$ 个整数 $a_1, a_2, \cdots, a_p$，表示每个机器人的初始位置。

接下来 $t$ 行，每行包含 1 个或 2 个正整数，描述一条指令。开头的整数 $\operatorname{op}$ 表示指令的类型。如果 $1 \leq \operatorname{op} \leq 2$，后面还会输入一个整数 $d$。

输出格式

对于每条指令 3，输出一个整数，即当前队列中机器人的数量。

3 4 3
-1 1 2
2 3
3
1 5
3

2
1

提示

样例 1 说明

一共有三个机器人。初始时，它们的位置分别是 $[-1,1,2]$。

• 第一次操作后，所有机器人向左移动 3 格，位置变成了 $[\underline{\bm{-4}},-2,-1]$。第一个机器人移出了数轴范围。

• 第二次操作后，输出当前机器人的数量，为 2 个。

• 第三次操作后，所有机器人向右移动 5 格，位置变成了 $[3,\underline{\bm{4}}]$。第二个机器人移出了数轴范围。

• 第四次操作后，输出当前机器人的数量，为 1 个。

数据规模与约定

• 对于 30% 的数据，$1 \leq p, t \leq 5\times 10^3$；

• 对于另外 20% 的数据，$1\le s\le 500$；

• 对于 100% 的数据，$1 \leq p, t \leq 3\times 10^5$，$1 \leq s, d \leq 2 \times 10^9$，$-s \le a_i \le s$。