P3373 [Template] Segment Tree 2

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.

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 several lines of integers, which are the results of all operation 3.

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