Ju-Jiang has $n$ headphones, arranged in a row and numbered from $1$ to $n$. Each headphone has a "metaphysical value," reflecting some of its indescribable unique properties. These metaphysical values are integers between $0$ and $m - 1$. Under external influences (including but not limited to changing cables, using an amplifier, switching to nuclear power, or having Uncle kAc tell them stories), the metaphysical values of these headphones change. Specifically, Ju-Jiang observed that each action $o$ corresponds to two integers $a_o$ and $b_o$, such that after this action, a headphone with a metaphysical value of $x$ will have its value changed to $(a_ox + b_o) \bmod m$.

Ju-Jiang is not satisfied with the performance of his headphones. Unfortunately, he is currently short on money and cannot afford to buy new ones to satisfy himself. Being tight on budget, he plans to devise a relatively economical scheme to improve the performance of his toys through various actions. Specifically, to complete the plan as quickly as possible, Ju-Jiang wants to efficiently perform the following tasks:

1. Ju-Jiang thought of an operation that changes a headphone's metaphysical value from $x$ to $(ax + b) \bmod m$, and he plans to apply this operation to headphones numbered $i$ through $j$.
2. Ju-Jiang wants to know what the metaphysical value of the $k$-th headphone would become if he were to perform (and only perform) his plans from the $i$-th to the $j$-th in order.

Out of the pride of a famous algorithm competition contestant, Ju-Jiang says he doesn't need your help. However, if Ju-Jiang truly gets tired of his toys, they will be sold to the Chairman for 50 yuan including shipping. To prevent the latter from getting a bargain, you have decided to step in after careful consideration.

Input

The first line contains a single integer representing the characteristics of this test case. The characteristic value is an integer between $0$ and $31$. We convert this integer into a five-bit binary number, where the lowest bit is the first bit.

If the first bit is $1$, it means the data is encrypted; otherwise, it is not. For encrypted data, you need to XOR the $i, j$ in the first type of operation and the $i, j, k$ in the second type of operation with the answer from the last query, $\text{lastans}$, to obtain the correct operation information. The initial value of $\text{lastans}$ is $0$.

If the second bit is $1$, it means modification operations of the form $(0x + b) \bmod m$ ($b \neq 0$) will appear; otherwise, they will not.

If the third bit is $1$, it means modification operations of the form $(ax + 0) \bmod m$ ($a \neq 0$) will appear; otherwise, they will not.

If the fourth bit is $1$, it means modification operations of the form $(ax + b) \bmod m$ ($a, b \neq 0$) will appear; otherwise, they will not.

If the fifth bit is $1$, we guarantee that the given $m$ is a prime number; otherwise, it is not guaranteed.

The second line contains two integers $n$ and $m$.

The third line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$, where $0 \leq a_i < m$, representing the initial metaphysical values of the $i$-th headphone.

The fourth line contains an integer $q$, representing the total number of Ju-Jiang's operations.

The following $q$ lines each contain $4$ or $5$ integers. The first integer cmd is $1$ or $2$, representing the type of operation. If cmd is $1$, it is followed by $4$ integers $i, j, a, b$, representing that Ju-Jiang adds a plan to apply the transformation $x \mapsto (ax + b) \bmod m$ to headphones $i \dots j$ (guaranteed $0 \leq a, b < m$). If cmd is $2$, it is followed by $3$ integers $i, j, k$, representing that Ju-Jiang asks what the final metaphysical value of the $k$-th headphone would be if he only applied transformations $i \dots j$. It is guaranteed that for both operations, after decryption (if the data is encrypted), $i \leq j$.

Output

For each type 2 operation, output a single integer on a new line representing the result of that query.

Examples

Input 1

24
3 5
1 2 3
5
1 1 2 3 2
1 2 3 4 3
2 1 1 3
1 1 3 1 4
2 1 3 2

Output 1

3
4

Input 2

7
3 5
1 2 3
5
1 1 2 0 3
1 2 3 4 0
2 1 1 3
1 2 0 2 0
2 2 0 1

Output 2

3
4

Input 3

See sample data download.

Constraints

Here, x can be either 0 or 1, and the leftmost bit of the characteristic value is the highest bit. We guarantee that in test cases of the same type, encrypted and unencrypted data points each account for 50%, the number of modification operations does not exceed $100000$, and all numbers can be stored in an int.

Due to the large amount of data in this problem, please use fast I/O. Due to the large number of test cases and the generous time limit, please minimize the number of submissions to this problem for the convenience of everyone.