Given a sequence of length $n$ and $m$ operations, each operation is one of the following:

1. Add $x$ to the range $[l, r]$.
2. For the range $[l, r]$, query:

$$a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p$$

Input

The first line contains two integers $n$ and $m$, representing the length of the sequence and the number of operations.

The next line contains $n$ integers representing the sequence.

The next $m$ lines each describe an operation, which can be one of the following:

• $1\ l\ r\ x$: Add $x$ to the range $[l, r]$.
• $2\ l\ r\ p$: Perform a query on the range $[l, r]$ with modulus $p$.

Output

For each query, output the result.

Examples

Input 1

6 4
1 2 3 4 5 6
2 1 2 10000007
2 2 3 5
1 1 4 1
2 2 4 10

Output 1

1
3
1

Input 2

5 5
2 3 3 3 3
1 1 1 530739835
2 1 1 8356089
2 1 4 5496738
1 1 2 66050181
1 2 4 138625417

Output 2

4306230
697527

Subtasks

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477

For 100% of the data, $n, m \le 500,000$, each number in the sequence is in the range $[1, 2 \cdot 10^9]$, $p \le 2 \cdot 10^7$, and each value added is in the range $[0, 2 \cdot 10^9]$.

There are 10 test cases in total.