有一个长度为 $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$ 表示满足 $y \le x$ 的最大整数 $y$。（例如 $\lfloor -2.5 \rfloor = -3$，$\lfloor -7 \rfloor = -7$）

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 100{,}000$），分别表示序列的长度和查询的个数。

第二行包含 $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

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