「Wdsr-2.5」小小的埴轮兵团
题目背景
杖刀偶磨弓是埴轮兵团的首长。
作为埴轮兵长,训练埴轮兵团是很平常的事情。
题目描述
磨弓下达命令让埴轮们站成一行。不妨认为它们站在了一个数轴上,每个埴轮的位置就是它脚下数轴的数字。磨弓会告诉你,第 $i$ 个埴轮的位置为 $a_i$ 。**不保证** $\bm {a_i}$ **升序**。
数轴的长度是有限制的,具体的范围是 $[-k,k]$ 。也就是说,如果某个埴轮移出了这个范围,它就脱离了这个队列了,并且不会再次回到队列当中。
为了训练埴轮,磨弓给埴轮们下达了 $m$ 个指令,有以下 3 种:
- 指令 1:**全体埴轮**向数轴的正方向移动 $x$ 个单位长度。
- 指令 2:**全体埴轮**往数轴的反方向移动 $x$ 个单位长度。
- 指令 3:依次报数,统计目前队列里一共有多少个埴轮。
但是磨弓发现,埴轮兵团的大小实在是太大了,以至于执行这些操作变得非常缓慢。尽管如此,磨弓仍然希望你告诉她所有指令 3 的结果。
输入输出格式
输入格式
第一行共有 $3$ 个整数 $n, m, k$,含义如题面所示。
第二行共有 $n$ 个整数 $a_1, a_2, \cdots, a_n$,表示每个埴轮的位置。
接下来 $m$ 行,有 $1$ 或者 $2$ 个正整数,描述一条指令。首先是一个整数 $\operatorname{op}$,表示这条指令的类型。如果 $1 \leq \operatorname{op} \leq 2$,接下来还会输入一个整数 $x$。
输出格式
对于每条指令 3 ,输出一个整数,表示目前还在队列中的埴轮的数目。
输入输出样例
输入样例 #1
3 4 3
-1 1 2
2 3
3
1 5
3
输出样例 #1
2
1
说明
#### 样例 1 说明
一共有三个埴轮。初始时,它们的站位分别是 $[-1,1,2]$ 。
- 第一次操作后,所有埴轮向左移动 $3$ 格,位置变成了 $[\underline{\bm{-4}},-2,-1]$ 。第一个埴轮被移出了数轴。
- 第二次操作后,输出当前的埴轮数目,为 $2$ 个。
- 第三次操作后,所有埴轮向右移动 $5$ 格,位置变成了 $[3,\underline \bm4]$ ,第二个埴轮被移出了数轴。
- 第四次操作后,输出当前的埴轮数目,为 $1$ 个。
#### 样例 2, 3
见下发附件。
#### 数据规模与约定
- 对于 $30\%$ 的数据,$1 \leq n, m \leq 5\times 10^3$;
- 对于另外 $20\%$ 的数据,$1\le k\le 500$;
- 对于 $100\%$ 的数据,$1 \leq n, m \leq 3\times 10^5$,$1 \leq k, x \leq 2 \times 10^9$,$-k \le a_i \le k$ 。