Cho dãy \(a\) gồm \(n\) phần tử.

Ta thực hiện \(q\) truy vấn có dạng là một trong các dạng như sau:

• Cho đoạn \([l,r]\), in ra tổng của đoạn \([l,r]\).
• Cho đoạn \([l,r]\) và một số \(x\), với mỗi phần tử \(i \in [l,r]\), gán \(a_i = a_i \mod x\).
• Cho số \(k\) và \(x\), gán \(a_k = x\).

Input

• Dòng đầu ghi \(2\) số nguyên dương \(n\) và \(q\).
• Dòng sau gồm \(n\) số nguyên dương \(a_1,a_2, ..., a_n\).
• \(q\) dòng sau, mỗi dòng gồm:
  • Số nguyên dương \(t\) là loại của truy vấn.
  • Nếu \(t=1\), nhận thêm hai số nguyên dương \(l,r\).
  • Nếu \(t=2\), nhận thêm ba số nguyên dương \(l,r,x\).
  • Nếu \(t=3\), nhận thêm hai số nguyên dương \(k,x\).

Constraints

• \(1 \le n,q \le 10^5\)
• \(1 \le a_1,a_2, ..., a_n \le 10^{9}\)
• \(1 \le x \le 10^9\).
• \(1 \le l \le r \le n\)

Output

• Với mỗi truy vấn, in ra kết quả tương ứng.

Sample Input 1

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

Sample Output 1

49
15
23
1
9