题目描述

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

7 3 7 2 5 3 0 3 1 2 1 1 4 3 1 4 7 4 2 1 7

*output*

2

### 样例 2
*input*

5 5 2 1 0 0 1 0 2 1 4 2 1 5 1 3 5 1 2 1 4 2 1 3

*output*

1 2 2 1

### 数据范围与提示
| 数据编号 |                   数据限制                   |     
| :--: | :--------------------------------------: |    
|  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$.