A5749. 「SHOI2011」改进代码

PP 写了两段对数组进行操作的代码。

对于 Pascal 选手，两段代码分别如下：

```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++ 选手，两段代码分别如下：
```c++
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 选手，代码如下：

```pascal
begin
operate1(1, 4, 3);
operate1(4, 7, 4);
operate2(1, 7);
end.
```

对于 C / C++ 选手，代码如下：

```c++
int main()
{
operate1(1, 4, 3);
operate1(4, 7, 4);
operate2(1, 7);
}
```

但是 QQ 觉得 PP 的程序效率太低了，他想请你优化 PP 的代码。即，对于一段只包含 operate1 、 operate2 两种语句的主程序以及运行之前数组 $a_i$ 的初始值，请你计算出他的输出。

输入的第一行包含三个整数 $n,m,p$ 。其中 $n$ 是操作中 $l,r$ 的上界， $m$ 是主程序中的语句数， $p$ 是程序中的常数 $p$ 的值。
接下去 $n$ 行每行一个整数，依次是 $ a_1,a_2,\dots,a_n$ 的初始化的值。输入保证这些值都在 $ 0,1,\dots,p-1$ 之中。
接下去 $m$ 行每行依次描述主程序的一行代码。每一行的格式为下面两者之一：
- 1 l r c : 表示代码 operate1(l, r, c); 。
- 2 l r : 表示代码 operate2(l, r); 。

输出即为输入对应的程序的输出。

| 数据编号 | 数据限制 |
| :--: | :--------------------------------------: |
| 1 | $ n \le 1000 , m\le 2000$ |
| 2~3 | $n\le 100000,m\le 200000,c\le1,a_i\le100000,p>500000$ |
| 4 | $n\le 100000,m\le 200000,l=1,r=n$ |
| 5~6 | $n\le 100000,m\le 200000$ 且对于所有 operate1 的参数都有 $l=1,r=n$ |
| 7~10 | $n\le 100000,m\le 200000$ |

保证 $1 \le l \le r \le n,0 \le c \le 10^8,p \le 10^6$.