長さ $n$ の数列 $A_0, A_1, \ldots, A_{n-1}$ があります。以下のクエリを実行するプログラムを作成してください。

• 1 l r c: 区間 $l \le i \le r$ のすべての $A_i$ に $c$ を加算する。
• 2 l r d: 区間 $l \le i \le r$ のすべての $A_i$ を $\lfloor A_i/d \rfloor$ で置き換える。
• 3 l r: 区間 $l \le i \le r$ の $A_i$ の最小値を出力する。
• 4 l r: 区間 $l \le i \le r$ の $A_i$ の総和を出力する。

ただし、$\lfloor x \rfloor$ は $x$ 以下の最大の整数 $y$ を表す（例：$\lfloor -2.5 \rfloor = -3$、$\lfloor -7 \rfloor = -7$）。

入力

最初の行には、数列の長さ $n$ とクエリの数 $q$ を表す 2 つの整数 $n$ と $q$ が含まれる（$1 \le n, q \le 100{,}000$）。

2 行目には、$n$ 個の整数 $A_0, A_1, \ldots, A_{n-1}$ が含まれる（$-10^9 \le A_i \le 10^9$）。

続く $q$ 行のそれぞれにはクエリが含まれる（$0 \le l \le r \le n-1$、$-10^4 \le c \le 10^4$、$2 \le d \le 10^9$）。

出力

タイプ 3 またはタイプ 4 のクエリが実行されるたびに、答えを 1 行に 1 つずつ出力せよ。

入出力例

入力例 1

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9

出力例 1

-2
-2
-2
-2
0
1
1