Given a sequence $a$ of $n$ non-negative integers, support the following two operations:

• 1 l r x: Divide all multiples of $x$ in the range $[l, r]$ by $x$.
• 2 l r: Query the sum of the range $[l, r]$.

This problem is online. Each $l, r, x$ must be XORed with the answer to the previous query. If there has been no previous query, the previous answer is $0$.

Input

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

The second line contains $n$ non-negative integers representing $a_i$.

The following $m$ lines each describe an operation:

• 1 l r x: Divide all multiples of $x$ in the range $[l, r]$ by $x$.
• 2 l r: Query the sum of the range $[l, r]$.

Output

For each query, output one integer per line representing the answer.

Examples

Input 1

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

Output 1

12

Constraints

$1 \leq n, m \leq 10^5$, $0 \leq a_i \leq 5 \times 10^5$. The decrypted $x, l, r$ satisfy $1 \leq x \leq 5 \times 10^5$ and $1 \leq l \leq r \leq n$.

Idea: nzhtl1477

Solution: nzhtl1477

Code: nzhtl1477, mrsrz

Data: nzhtl1477, mrsrz