길이가 $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$)가 주어진다.

둘째 줄에는 $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번 쿼리가 주어질 때 마다 정답을 한 줄에 하나씩 출력한다.

Sample

Input

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

Output

-2
-2
-2
-2
0
1
1