Description

PP wrote two pieces of code to operate on an array.

For Pascal users, the two procedures 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++ users, the two functions 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);
}

Then, the main program can operate on the array $a_i$ by calling these two subroutines. The following is sample code.

For Pascal users, the code is:

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

For C / C++ users, the code is:

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

However, QQ thinks PP’s program is too slow, and he wants you to optimize PP’s code. That is, given a main program that contains only two kinds of statements, operate1 and operate2, and the initial values of the array $a_i$ before running, please compute the output of the program.

Input Format

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

In the next $n$ lines, each line contains one integer, which are the initial values of $a_1, a_2, \ldots, a_n$ in order. The input guarantees that these values are all within $0, 1, \ldots, p - 1$.

In the next $m$ lines, each line describes one line of code in the main program. Each line has one of the following two formats:

• 1 l r c: represents the statement operate1(l, r, c);.
• 2 l r: represents the statement operate2(l, r);.

Output Format

Output the output produced by the program corresponding to the given input.

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

Hint

Constraints and notes

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

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

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

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

Test points $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$.

Translated by ChatGPT 5