Problem Description

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

• 1 l r x: For all numbers in the interval $[l,r]$ that are multiples of $x$, divide them by $x$.
• 2 l r: Query the sum of the interval $[l,r]$.

This problem is forced online. For each operation, the values $l, r, x$ need to be XORed with the previous answer. If there has been no previous query, then the previous answer is $0$.

Input Format

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

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

Then follow $m$ lines, each describing one operation.

• 1 l r x: For all numbers in the interval $[l,r]$ that are multiples of $x$, divide them by $x$.
• 2 l r: Query the sum of the interval $[l,r]$.

Output Format

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

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

12

Hint

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$, $1\leq l\leq r\leq n$.

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, mrsrz, Data: nzhtl1477, mrsrz, 一只绝帆.

Translated by ChatGPT 5