题目描述

蜿蜒的长城连绵不绝，长城上的很多位置都有士兵把守。我们把指挥士兵的将军定为原点，那么在它东边的士兵位置就是正值，在它西边的士兵位置就是负值，整个长城的范围区间为 \([-k,k]\)。现在给定 \(n\) 个士兵的位置，为了保持战斗力，将军决定开始训练士兵，让士兵在长城上巡逻，如果士兵巡逻的范围超出了 \([-k,k]\) 这个区间，那么士兵就不能再回到长城上了，将军发出 \(3\) 种指令：

1 x:表示全体士兵向东移动 \(x\) 个单位长度。

2 x:表示全体士兵向西移动 \(x\)个单位长度。

3:表示询问当前长城上还有多少组士兵。

现在请输出所有的指令 \(3\) 的结果。

格式

输入格式

输入第 \(1\) 行 \(3\) 个整数 \(n,m,k\);

输入第 \(2\) 行有 \(n\) 个整数 \(a_1,a_2,……a_n\)，表示每个士兵的位置。

接下来 \(m\) 行，每行有 \(1\) 个或 \(2\) 个正整数，第一个整数 \(op\) 表示指令种类，如果 \(op\) 为 \(1\) 或 \(2\)，则还会输入 \(1\) 个整数 \(x\)，表示移动的长度。

输出格式

输出若干行，每行一个整数，表示对应的指令 \(3\) 的输出结果。

样例1

输入样例1

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

输出样例1

2
1

限制

对于 \(100\%\) 的数据， \(1<=n,m<=300000,1<=k<=2*10^9;1<=x<=5*10^5; -k<=ai<=k\);

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T2\)