Background

http://sukasuka-anime.com/

Can't quit the Chtholly addiction.

Sqrt decomposition that I just can't pull off.

Oh, by the way, are there any "Ke-ologists" who want to buy the BD? Please support Moyu~.

Or does anyone want to join a figure crowdfunding?

Problem Description

Give Chtholly a non-negative sequence $a$ of length $n$, supporting the following two operations:

• $\verb!1 l r x!$: Divide all multiples of $x$ in the interval $[l,r]$ by $x$.
• $\verb!2 l r!$: Query the sum of elements in the interval $[l,r]$.

Chtholly is very cute, so you should help her solve this problem.

Input Format

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

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

Then there are $m$ lines, each describing one operation:

• $\verb!1 l r x!$: Divide all multiples of $x$ in the interval $[l,r]$ by $x$.
• $\verb!2 l r!$: Query the sum of elements in the interval $[l,r]$.

Output Format

For each query, output one line with one number denoting the answer.

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

15
12

Hint

Constraints

$1 \le n , m \le 10^5$, $0 \le a_i \le 5\times 10^5$, $1 \le x \le 5\times 10^5$.

Translated by ChatGPT 5