Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\). Bạn cần thực hiện \(Q\) truy vấn thuộc ba loại sau:

• 1 l r: Tính tổng các phần tử trong đoạn từ \(l\) đến \(r\), tức là \(\sum_{i=l}^r A_i\).
• 2 l r x: Thực hiện phép toán lấy dư cho tất cả các phần tử trong đoạn từ \(l\) đến \(r\) với \(x\), tức là \(A_i = A_i \bmod x\) với mọi \(l \le i \le r\).
• 3 k x: Gán giá trị của phần tử tại vị trí \(k\) bằng \(x\), tức là \(A_k = x\).

Đầu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong ba định dạng trên. Các giá trị \(l, r, k, x\) thỏa mãn \(1 \le l \le r \le N\), \(1 \le k \le N\), \(1 \le x \le 10^9\).

Đầu ra

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

Chấm điểm

• Subtask duy nhất (100% số điểm): Không có ràng buộc gì thêm (\(N, Q \le 10^5\), \(A_i, x \le 10^9\)).

Ví dụ

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

15
6
15