407687: GYM102875 A Array

Yukikaze received an array $$$(a_1, a_2, \cdots a_n)$$$ as a gift. She decided to play with it. The game consists of $$$q$$$ turns. In each turn, she will perform some kind of operation (listed below) on all elements in a subarray of $$$a$$$.

1. Given $$$l, r, k$$$, for every element $$$a_i$$$ in subarray $$$(a_l, a_{l+1}, \cdots a_r)$$$, replace $$$a_i$$$ by $$$a_i+k$$$.
2. Given $$$l, r, k$$$, for every element $$$a_i$$$ in subarray $$$(a_l, a_{l+1}, \cdots a_r)$$$, replace $$$a_i$$$ by $$$a_i \times k$$$.
3. Given $$$l, r, k$$$, for every element $$$a_i$$$ in subarray $$$(a_l, a_{l+1}, \cdots a_r)$$$, replace $$$a_i$$$ by $$$a_i^k$$$.
4. Given $$$l, r, k$$$, find the sum of the $$$k$$$-th powers of elements in the subarray $$$(a_l, a_{l+1}, \cdots a_r)$$$. In other words, find the value of $$$\displaystyle \sum_{i=l}^r a_i^k$$$.
5. Given $$$l, r$$$, find the product of all elements in the subarray $$$(a_l, a_{l+1}, \cdots a_r)$$$. In other words, find the value of $$$\displaystyle \prod_{i=l}^ra_i$$$.

In this problem, we define that $$$0^0 = 1$$$.

Since the result of operations of the last two kinds may be large, you only have to find it modulo a small integer $$$p$$$.

The first line of the input contains two integers $$$n,p\ (1 \leq n \leq 10^5, 2 \leq p \leq 30)$$$, denoting the number of elements in the array $$$a$$$ and the modulus for the operations of type 4 and 5.

The next line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n\ (0 \leq a_i \leq 10^9)$$$, denoting the initial elements in the array $$$a$$$.

The third line contains one integer $$$q\ (1 \leq q \leq 10^5)$$$, denoting the number of operations to be performed.

Each of the following $$$q$$$ lines contains $$$4$$$ integers $$$t, l, r, k\ (1 \leq t \leq 5, 1 \leq l \leq r \leq n, 0 \leq k \leq 10^9)$$$ represents an operation of kind $$$t$$$. Note that if $$$t = 5$$$, it's guaranteed that $$$k = 0$$$.

For each operation of type 4 or 5, output the result modulo $$$p$$$ as an integer in a single line.

5 29
5 2 4 1 3
9
4 2 4 1
1 1 3 2
2 2 4 3
3 3 5 2
5 3 3 0
4 1 5 2
2 3 5 0
3 2 4 0
4 3 4 1

7
5
3
2