Cho dãy số $A_0, A_1, \ldots, A_{n-1}$ có độ dài $n$. Viết chương trình thực hiện các truy vấn sau:

• 1 l r c: Cộng $c$ vào tất cả $A_i$ trong đoạn $l \le i \le r$.
• 2 l r d: Thay tất cả $A_i$ trong đoạn $l \le i \le r$ bằng $\lfloor A_i/d \rfloor$.
• 3 l r: Đưa ra giá trị nhỏ nhất của tất cả $A_i$ trong đoạn $l \le i \le r$.
• 4 l r: Đưa ra tổng của tất cả $A_i$ trong đoạn $l \le i \le r$.

trong đó $\lfloor x \rfloor$ ký hiệu số nguyên lớn nhất $y$ thỏa mãn $y \le x$ (ví dụ: $\lfloor -2.5 \rfloor = -3$, $\lfloor -7 \rfloor = -7$).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($1 \le n, q \le 100{,}000$), cho biết độ dài dãy số và số lượng truy vấn.

Dòng thứ hai chứa $n$ số nguyên $A_0, A_1, \ldots, A_{n-1}$ ($-10^9 \le A_i \le 10^9$).

Mỗi dòng trong $q$ dòng tiếp theo chứa một truy vấn ($0 \le l \le r \le n-1$, $-10^4 \le c \le 10^4$, $2 \le d \le 10^9$).

Dữ liệu ra

Mỗi khi gặp truy vấn loại 3 hoặc loại 4, in ra một kết quả trên một dòng.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

-2
-2
-2
-2
0
1
1