Given a sequence $a$ of length $n$, there are $m$ operations.

There are two types of operations:

1 l r x: For all $i$ in the range $[l, r]$, replace $a_i$ with $\gcd(a_i, x)$.

2 l r: Query the sum of the range $[l, r]$, outputting the answer modulo $2^{32}$.

Input

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

The second line contains $n$ integers representing $a_i$.

The following $m$ lines each contain three or four integers, representing an operation.

Output

For each type $2$ operation, output one integer per line representing the answer to the query.

Examples

Input 1

10 10
4 1 5 10 1 3 8 2 8 2  
2 1 7
2 1 10
1 7 10 4
1 5 8 10
2 1 8
1 3 5 2
1 3 4 3
2 5 8
2 3 7
2 6 10

Output 1

32
44
26
6
6
11

Subtasks

Idea: nzhtl1477, Solution: nhtl1477, Code: ccz181078, Data: ccz181078

For $20\%$ of the data, $1 \le n, m, a_i, x \le 10^3$.

For $50\%$ of the data, $1 \le n, m \le 10^5$, and the elements of $a$ and the $x$ in each operation are generated randomly.

For another $20\%$ of the data, all queries occur after all modifications.

For $100\%$ of the data, $1 \le n \le 2 \cdot 10^5$, $1 \le m \le 5 \cdot 10^5$, and all values are integers in the range $[1, 10^{18}]$.