Description

As stated, given a sequence $a$, you need to perform the following three operations:

• Multiply every number in a given interval by $x$.
• Add $x$ to every number in a given interval.
• Find the sum of every number in a given interval.

Input Format

The first line contains three integers $n, q, m$, representing the number of elements in the sequence, the total number of operations, and the modulus.

The second line contains $n$ space-separated integers, where the $i$-th number is the initial value $a_i$ of the $i$-th element.

Each of the next $q$ lines contains several integers describing an operation, as follows:

Operation 1: Format: 1 x y k Meaning: multiply every number in the interval $[x,y]$ by $k$.

Operation 2: Format: 2 x y k Meaning: add $k$ to every number in the interval $[x,y]$.

Operation 3: Format: 3 x y Meaning: output the sum of every number in the interval $[x,y]$ modulo $m$.

Output Format

Output several lines of integers, which are the results of all operation 3.

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

17
2

Hint

Constraints:

For $30\%$ of the testdata: $n \le 8$, $q \le 10$. For $70\%$ of the testdata: $n \le 10^3$, $q \le 10^4$. For $100\%$ of the testdata: $1 \le n \le 10^5$, $1 \le q \le 10^5$, $1 \le a_i, k \le 10^4$.

Except for the samples, $m = 571373$.

(The testdata has been strengthened ^_^.)

Sample explanation:

Therefore, the outputs should be $17$ and $2$ ($40 \bmod 38 = 2$).

Translated by ChatGPT 5