P2023 [AHOI2009] Maintain Sequence

The teacher gave Xiao Keke a task to maintain a sequence, and now he hopes you can help him complete it.

There is a sequence of length $n$, $\{a_i\}$, with the following three types of operations: 1. Format `1 t g c`: set all $a_i$ with $t \le i \le g$ to $a_i \times c$. 2. Format `2 t g c`: set all $a_i$ with $t \le i \le g$ to $a_i + c$. 3. Format `3 t g`: query the sum of all $a_i$ with $t \le i \le g$. Since the answer may be large, you only need to output this sum modulo $p$.

The first line contains two integers $n$ and $p$. The second line contains $n$ non-negative integers, representing the sequence $\{a_i\}$. The third line contains an integer $m$, the total number of operations. From the fourth line on, each line describes one operation. In the same line, adjacent numbers are separated by a single space, and there are no extra spaces at the beginning or end.

For each operation of type 3, in the order they appear in the input, output one integer per line representing the query result.

#### Explanation for Sample Input/Output 1 - Initially, the sequence is $\{1,2,3,4,5,6,7\}$. - After the 1st operation, the sequence becomes $\{1,10,15,20,25,6,7\}$. - For the 2nd operation, the sum is $10+15+20=45$, and $45 \bmod 43 = 2$. - After the 3rd operation, the sequence becomes $\{1,10,24,29,34,15,16\}$. - For the 4th operation, the sum is $1+10+24=35$, and $35 \bmod 43 = 35$. - For the 5th operation, the sum is $29+34+15+16=94$, and $94 \bmod 43 = 8$. #### Constraints The testdata scale is as follows: | Data point ID | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,10 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $n=$ | $10$ | $1000$ | $1000$ | $10000$ | $60000$ | $70000$ | $80000$ | $90000$ | $100000$ | | $m=$ | $10$ | $1000$ | $1000$ | $10000$ | $60000$ | $70000$ | $80000$ | $90000$ | $100000$ | For all test points, it is guaranteed that $0 \le p, a_i, c \le 10^9$, $1 \le t \le g \le n$. Translated by ChatGPT 5