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

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$ 的初始值，请你计算出他的输出。

输入的第一行包含三个整数 $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$.