Khôi phục dãy số

Vào ngày Quốc tế Thiếu nhi, một đứa trẻ đã đến nhà của Picks và làm rối tung mọi thứ. Picks rất tức giận, bởi nhiều vật quan trọng đã biến mất, trong đó có dãy số yêu thích của anh ấy.

May mắn thay, Picks vẫn nhớ cách khôi phục lại dãy số. Ban đầu, anh ấy tạo ra một mảng số nguyên \(a[1], a[2], \ldots, a[n]\). Sau đó, anh ấy thực hiện \(m\) thao tác trên mảng này. Mỗi thao tác có thể là một trong ba loại sau:

• In tổng: 1 l r --- Picks muốn biết tổng các phần tử trong đoạn từ \(l\) đến \(r\) (tức là \(\sum\limits_{i=l}^{r} a[i]\)).
• Lấy dư: 2 l r x --- Với mỗi \(i\) trong đoạn \([l, r]\), thay \(a[i]\) bằng \(a[i] \bmod x\).
• Gán giá trị: 3 k x --- Gán giá trị \(a[k] := x\).

Bạn hãy giúp Picks thực hiện tất cả các thao tác, và in ra đáp án tương ứng với các thao tác loại 1.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m\) \((1 \le n, m \le 10^5)\) --- số phần tử ban đầu và số thao tác cần thực hiện.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\) --- các phần tử ban đầu của mảng.

• Mỗi dòng trong số \(m\) dòng tiếp theo là một thao tác, theo một trong các định dạng sau:

• 1 $l$ $r$ \((1 \le l \le r \le n)\) --- thao tác loại 1 (in tổng đoạn).

• 2 $l$ $r$ $x$ \((1 \le l \le r \le n, 1 \le x \le 10^9)\) --- thao tác loại 2 (lấy dư đoạn).
• 3 $k$ $x$ \((1 \le k \le n, 1 \le x \le 10^9)\) --- thao tác loại 3 (gán giá trị tại vị trí).

Output

Với mỗi thao tác loại 1, in ra một dòng chứa tổng các phần tử trong đoạn tương ứng. Chú ý: Tổng này có thể vượt quá giới hạn của số nguyên 32-bit.

Example

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

8
5

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

49
15
23
1
9

Scoring

• Có \(30\%\) số điểm có \(n, m \leq 1000\).
• Có \(30\%\) số điểm trong các test không có truy vấn loại \(2\).
• \(40\%\) số điểm không có ràng buộc gì thêm.