Cho dãy số nguyên dương a độ dài N, xử lý Q truy vấn gồm 1 trong 3 dạng:

• 1 l r: Tính (1 ≤ l ≤ r ≤ N).

• 2 p x: Gán a[p] = x (1 ≤ p ≤ N, 1 ≤ x ≤ ~10^9~).

• 3 l r x: Gán a[i] = a[i] mod x (l ≤ i ≤ r, 1 ≤ x ≤ ~10^9~).

Dữ liệu:

Input:

• Dòng 1: Số nguyên dương N và Q (1 ≤ N, Q ≤ ~10^5~).
• Dòng 2: N số nguyên dương biểu diễn dãy a (1 ≤ a[i] ≤ ~10^9~).
• Dòng 3: Q+2: Mỗi dòng là một truy vấn.

Output:

• Với mỗi truy vấn loại 1, in kết quả trên 1 dòng.

Input

5 5
5 4 3 2 1
3 3 5 2
2 3 3
1 1 5
3 1 5 1
1 2 4

Output

13
0