Cho mảng \(A\) 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 một trong ba loại sau:

• \(1 \ l \ r \ x\): Gán \(A_i \leftarrow A_i \bmod x\) với mọi \(i\) thuộc đoạn \([l, r]\).
• \(2 \ l \ r \ x\): Gán \(A_i \leftarrow x\) với mọi \(i\) thuộc đoạn \([l, r]\).
• \(3 \ l \ r\): Tính tổng \(\sum_{i=l}^r A_i\).

Đầu vào

• Dòng đầu tiên chứa hai số nguyên dương \(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 định dạng nêu trên (\(1 \le l \le r \le N\), \(1 \le x \le 10^9\)).

Đầu ra

• Với mỗi truy vấn loại 3, in ra một dòng duy nhất chứa kết quả của phép tính.

Giới hạn

• Trong tất cả các testcase, \(1 \le N, Q \le 10^5\) và \(1 \le A_i, x \le 10^9\).

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

6
17