Description

Original source: AHOI 2009

The teacher assigned Xiaokeke the task of maintaining a number sequence, and now Xiaokeke hopes you can help him complete it.

There is a sequence of length $n$, denoted as $a_1,a_2,\cdots ,a_n$. There are three types of operations:

• Multiply all numbers in a segment of the sequence by a value;
• Add a value to all numbers in a segment of the sequence;
• Query the sum of numbers in a segment of the sequence. Since the answer may be very large, you only need to output the result modulo $P$.

Input Format

The first line contains two integers $n$ and $P$;

The second line contains $n$ non-negative integers, from left to right as $a_1,a_2,\cdots ,a_n$;

The third line contains an integer $M$, representing the total number of operations;

Starting from the fourth line, each line describes an operation. The input operations are in the following three forms:

• Operation $1$: 1 t g c, which means changing all $a_i$ satisfying $t\le i\le g$ to $a_i\times c$;
• Operation $2$: 2 t g c, which means adding $c$ to all $a_i$ satisfying $t\le i\le g$;
• Operation $3$: 3 t g, which queries the sum of all $a_i$ satisfying $t\le i\le g$ modulo $P$.

Adjacent numbers on the same line are separated by a single space, and there are no extra spaces at the beginning or end of each line.

Output Format

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

Sample 1

Initially, the sequence is $\{1,2,3,4,5,6,7\}$;

After the first operation, the sequence becomes $\{1,10,15,20,25,6,7\}$;

For the second operation, the sum is $10+15+20=45$, and the result modulo $43$ is $2$;

After the third operation, the sequence becomes $\{1,10,24,29,34,15,16\}$;

For the fourth operation, the sum is $1+10+24=35$, and the result modulo $43$ is $35$;

For the fifth operation, the sum is $29+34+15+16=94$, and the result modulo $43$ is $8$.

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

Data Range and Hints

For all test data, $1\le t\le g\le n,0\le c,a_i\le 10^9,1\le P\le 10^9+7$.

The scale of the test data is as follows: