题目描述

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

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); 。

输出格式

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

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

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

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$​​.