[ABC256Ex] I like Query Problem

给定 $ 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 $。

[problemUrl]: https://atcoder.jp/contests/abc256/tasks/abc256_h $ 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 $

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

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 $ になります。