Problem Description

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

Each time, there are two types of operations:

1 l r x: For all $i$ in the interval $[l,r]$, set $a_i$ to $\gcd(a_i,x)$.

2 l r: Query the sum of the interval $[l,r]$, and output the answer modulo $2^{32}$.

Input Format

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

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

Then follow $m$ lines, each containing three or four integers, describing one operation.

Output Format

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

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

32
44
26
6
6
11

Hint

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

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

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

For another $20\%$ of the testdata, all queries happen after modifications.

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

Translated by ChatGPT 5