問題文

長さ $N$ の配列 $A=(A_0,A_1,...,A_{N-1})$ が与えられます。ここで、各 $A_i$ は $0$ 以上の整数です。

次の $3$ 種類のクエリを合計 $Q$ 回処理してください。 ここで、$\text{isqrt}(x)$ は $\sqrt{x}$ の整数部分を返す関数、つまり $\text{isqrt}(x) := \left\lfloor \sqrt{x}\right\rfloor$ です。

• 0 l r :$\ A_l+A_{l+1}+...+A_{r-1}$ を出力する。
• 1 l r x : $\ A_l,A_{l+1},...,A_{r-1}$ に $x$ を代入する。
• 2 l r :$\ A_l,A_{l+1},...,A_{r-1}$ の全てに $\text{isqrt}$ を作用させる。すなわち、$l \le i < r$ を満たす全ての $i$ に対して、$A_i$ を $\text{isqrt}(A_i)$ に置き換える。

制約

• $1 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $0 \le A_i \le 10^9$
• $0 \le l \le r \le N$
• $0 \le x\le 10^9$
• 入力は全て整数

入力

$N$ $Q$
$A_0$ $A_1$ ... $A_{N-1}$
$\text{query}_1$
$\text{query}_2$
...
$\text{query}_Q$

ただし、$\text{query}_i$は $i$ 個目のクエリを表し、以下のいずれかの形式で与えられる。

$0 ~ l ~ r$

$1 ~ l ~ r ~ x$

$2 ~ l ~ r$

出力

1種類目のクエリの数を $k$ として、$k$ 行出力せよ。 $i$ 行目には $i$ 番目の1種類目のクエリに対する解答を出力せよ。

サンプル

6 4
1 2 3 4 5 6
0 1 4
1 0 3 10
2 1 3
0 1 4

9
10