题目描述

$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$ を出力する。

输入格式

入力は以下の形式で標準入力から与えられる。ここで$\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$

输出格式

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

题目大意

给定 $n, q$，和序列 $a_n$，给定 $q$ 次操作，有三种：

1 L R x：对于 $[L, R]$ 内的所有 $i$ 进行 $a_i \leftarrow \lfloor \dfrac{a_i}{x} \rfloor$。

2 L R y：区间推平 $[L, R]$ 为 $y$。

3 L R：输出 $\sum_{i = L}^R a_i$。

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

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

提示

制約

• $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$
• 入力される値はすべて整数

Sample Explanation 1

はじめ、$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$ になります。