AT_abc256_h [ABC256Ex] I like Query Problem

[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 $

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

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