Problem Description

PP has written two segments of code for array operations.

For Pascal programmers, the codes are as follows:

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;

For C/C++ programmers, the codes are as follows:

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

The main program can call these two subroutines to operate on array $a_i$. Here is an example code.

For Pascal programmers, the code is as follows:

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

For C/C++ programmers, the code is as follows:

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

However, QQ thinks PP's program is too inefficient. He wants you to optimize PP's code. That is, for a main program containing only operate1 and operate2 statements and the initial values of array $a_i$, please calculate the output.

Input Format

The first line of input contains three integers $n, m, p$. Here, $n$ is the upper bound for $l, r$ in operations, $m$ is the number of statements in the main program, and $p$ is the constant value $p$ in the program.

The next $n$ lines each contain one integer, which are the initial values of $a_1, a_2, \ldots, a_n$. It is guaranteed that these values are within $0, 1, \ldots, p-1$.

The next $m$ lines each describe a line of code in the main program. Each line is in one of the following formats:

• 1 l r c: Represents the code operate1(l, r, c);.
• 2 l r: Represents the code operate2(l, r);.

Output Format

The output is the output of the program corresponding to the input.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #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

Sample Output #2

1
2
2
1

Notes/Hints

Data Range and Hints

Test case $1$: $n \le 1000, m \le 2000$.

Test cases $2 \sim 3$: $n \le 100000, m \le 200000, c \le 1, a_i \le 100000, p > 500000$.

Test case $4$: $n \le 100000, m \le 200000, l = 1, r = n$.

Test cases $5 \sim 6$: $n \le 100000, m \le 200000$ and for all operate1 parameters, $l = 1, r = n$.

Test cases $7 \sim 10$: $n \le 100000, m \le 200000$.

It is guaranteed that $1 \le l \le r \le n, 0 \le c \le 10^8, p \le 10^6$.

见题面 Input 部分

见题面 Output 部分