Problem Description

You are playing a galgame, but you find the story incomprehensible, so you decide to drop the game and start working on a data structure problem instead:

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

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

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

Input Format

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

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

The following $m$ lines describe the operations, which can be one of the following:

• $1\ l\ r\ x$ indicates adding $x$ to the interval $[l, r]$;
• $2\ l\ r\ p$ indicates querying the interval $[l, r]$ with modulo $p$.

Output Format

For each query, output a single number representing the answer.

Sample Input and Output

Input Sample #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 Sample #1

1
3
1

Input Sample #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 Sample #2

4306230
697527

Notes/Hints

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

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

There are 10 test cases in total.

见题面 Input 部分

见题面 Output 部分