Description

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

Input Format

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.

Output Format

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

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

2
35
8

Hint

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:

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