P3987 I Will Always Love Chtholly~

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?

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.

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]$.

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

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