JYY has a task involving the maintenance of a sequence. He hopes you can help him complete it.

JYY currently has a sequence of length $N$, $a_1, a_2, \dots, a_N$, and there are three types of operations:

1. Multiply all numbers in a range of the sequence by a value;
2. Add a value to all numbers in a range of the sequence;
3. Query the sum of a range of numbers in the sequence.

Since the answer can be very large, for each query, you only need to tell JYY the result of the answer modulo $P$.

Input

The first line of the input contains two positive integers, $N$ and $P$; The second line contains $N$ non-negative integers, which are $a_1, a_2, \dots, a_N$ from left to right. The third line contains an integer $M$, representing the total number of operations. The next $M$ lines each satisfy one of the following three forms:

1. "1 $t$ $g$ $c$": Multiply all $a_i$ satisfying $t \le i \le g$ by $c$;
2. "2 $t$ $g$ $c$": Add $c$ to all $a_i$ satisfying $t \le i \le g$;
3. "3 $t$ $g$": Query the sum of $a_i$ satisfying $t \le i \le g$ modulo $P$.

Output

For each operation starting with 3, output the corresponding result on a new line.

Examples

Input 1

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

Output 1

2
35

Note

The initial sequence is $(1, 2, 3, 4, 5, 6, 7)$. After the 1st operation, the sequence is $(1, 10, 15, 20, 25, 6, 7)$. For the 2nd operation, the sum is $10+15+20=45$, and the result modulo 43 is 2. After the 3rd operation, the sequence is $(1, 10, 24, 29, 34, 15, 16)$. For the 4th operation, the sum is $1+10+24=35$, and the result modulo 43 is 35. For the 5th operation, the sum is $29+34+15+16=94$, and the result modulo 43 is 8.

Constraints

For 30% of the data, $N \le 1000$; For 100% of the data, $1 \le N, M \le 10^5$, $1 \le P, c, a_i \le 2 \times 10^9$, $1 \le t \le g \le N$.