配点 : $600$ 点

問題文

$N, Q$ および $A = (a_1, a_2, \dots, a_N)$ が与えられます。 以下で説明されるクエリを $Q$ 個処理してください。クエリは次の $3$ 種類のいずれかです。

• 1 L R x : $i=L,L+1,\dots,R$ について $a_i$ の値を $\displaystyle \left\lfloor \frac{a_i}{x} \right\rfloor$ に更新する。
• 2 L R y : $i=L,L+1,\dots,R$ について $a_i$ の値を $y$ に更新する。
• 3 L R : $\displaystyle\sum_{i=L}^R a_i$ を出力する。

制約

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq L \leq R \leq N$
• $1 \leq a_i \leq 10^5$
• $2 \leq x \leq 10^5$
• $1 \leq y \leq 10^5$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで$\text{query}_i$ は $i$ 番目に処理するクエリである。

$N$ $Q$

$a_1$ $a_2$ $\dots$ $a_N$

$\text{query}_1$

$\text{query}_2$

$\vdots$

$\text{query}_Q$

各クエリは以下の $3$ 種類のいずれかの形式で与えられる。

$1$ $L$ $R$ $x$

$2$ $L$ $R$ $y$

$3$ $L$ $R$

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

3 5
2 5 6
3 1 3
1 2 3 2
3 1 2
2 1 2 3
3 1 3

13
4
9

はじめ、$A = (2, 5, 6)$ です。よって $1$ 番目のクエリの答えは $a_1 + a_2 + a_3 = 2 + 5 + 6 = 13$ になります。 $2$ 番目のクエリを処理した直後は $A = (2, 2, 3)$ です。よって $3$ 番目のクエリの答えは $a_1 + a_2 = 2 + 2 = 4$ になります。 $4$ 番目のクエリを処理した直後は $A = (3, 3, 3)$ です。よって $5$ 番目のクエリの答えは $a_1 + a_2 + a_3 = 3 + 3 + 3 = 9$ になります。

6 11
10 3 5 20 6 7
3 1 6
1 2 4 3
3 1 3
2 1 4 10
3 3 6
1 3 6 2
2 1 4 5
3 1 6
2 1 3 100
1 2 5 6
3 1 4

51
12
33
26
132