[SHOI2011] 改进代码
题目描述
PP 写了两段对数组进行操作的代码。
对于 Pascal 选手，两段代码分别如下：
```
procedure operate1(l, r, c : longint);
var
i : longint;
begin
for i := l to r do
a[i] := (a[i] + c) mod p;
end;
procedure operate2(l, r : longint);
var
i, cnt : longint;
begin
cnt := 0;
for i := l to r - 1 do
if a[i] > a[i + 1]
then cnt := cnt + 1;
writeln(cnt);
end;
```
对于 C / C++ 选手，两段代码分别如下：
```cpp
void operate1(int l, int r, int c)
{
int i;
for (i = l; i <= r; ++i)
a[i] = (a[i] + c) % p;
}
void operate2(int l, int r)
{
int i, cnt = 0;
for (i = l; i < r; ++i)
if (a[i] > a[i + 1])
++ cnt;
printf("%d\n", cnt);
}
```
于是，主程序就可以通过调用这两个子程序对数组 $a_i$ 进行操作，下面是示例代码。
对于 Pascal 选手，代码如下：
```
begin
operate1(1, 4, 3);
operate1(4, 7, 4);
operate2(1, 7);
end.
```
对于 C / C++ 选手，代码如下：
```
int main()
{
operate1(1, 4, 3);
operate1(4, 7, 4);
operate2(1, 7);
}
```
但是 QQ 觉得 PP 的程序效率太低了，他想请你优化 PP 的代码。即，对于一段只包含 ``operate1`` 、 ``operate2`` 两种语句的主程序以及运行之前数组 $a_i$ 的初始值，请你计算出他的输出。
输入输出格式
输入格式
输入的第一行包含 $3$ 个整数 $n,m,p$ 。其中 $n$ 是操作中 $l,r$ 的上界， $m$ 是主程序中的语句数， $p$ 是程序中的常数 $p$ 的值。
接下去 $n$ 行每行一个整数，依次是 $a_1,a_2,…,a_n$ 的初始化的值。输入保证这些值都在 $0,1,…,p-1$ 之中。
接下去 $m$ 行每行依次描述主程序的一行代码。每一行的格式为下面两者之一：
- ``1 l r c`` : 表示代码 ``operate1(l, r, c);`` 。
- ``2 l r`` : 表示代码 ``operate2(l, r);`` 。
输出格式
输出即为输入对应的程序的输出。
输入输出样例
输入样例 #1
7 3 7
2
5
3
0
3
1
2
1 1 4 3
1 4 7 4
2 1 7输出样例 #1
2输入样例 #2
5 5 2
1
0
0
1
0
2 1 4
2 1 5
1 3 5 1
2 1 4
2 1 3输出样例 #2
1
2
2
1说明
**数据范围与提示**
测试点 $1$：$n \le 1000,m \le 2000$。
测试点 $2 \sim 3$：$n \le 100000$,$m \le 200000$,$c \le 1$,$a_i \le 100000$,$p>500000$。
测试点 $4$：$n \le 100000,m \le 200000,l=1,r=n$。
测试点 $5 \sim 6$：$n \le 100000,m \le 200000$ 且对于所有 ``operate1`` 的参数都有 $l=1,r=n$。
测试点 $7 \sim 10$：$n \le 100000,m \le 200000$。
保证 $1 \le l \le r \le n,0 \le c \le 10^8,p \le 10^6$.