Cho dãy ~A~ gồm ~N~ số nguyên được đánh số từ ~1~ đến ~N~. Thực hiện ~Q~ truy vấn thuộc một trong ba loại sau:

• Loại ~1~ có dạng 1 X Y Z ~(1 \le X \le Y \le N~ ; ~2 \le Z \le 10^5)~: Cập nhật ~A_i = \lfloor \frac{A_i}{Z} \rfloor~ với mỗi ~i~ thỏa mãn ~X \le i \le Y~.
• Loại ~2~ có dạng 2 P Q V ~(1 \le P \le Q \le N~ ; ~1 \le V \le 10^5)~: Cập nhật ~A_j = V~ với mỗi ~j~ thỏa mãn ~P \le j \le Q~.
• Loại ~3~ có dạng 3 L R ~(1 \le L \le R \le N)~: Tính giá trị biểu thức ~ \displaystyle \sum_{k=L}^{R}A_k~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N \le 5 \times 10^5~ ; ~1 \le Q \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên của dãy ~A~ ~(1 \le A_i \le 10^5)~.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong ba loại trên.
• Dữ liệu đảm bảo có ít nhất một truy vấn loại ~3~.

Output

• Với mỗi truy vấn loại ~3~, in ra giá trị biểu thức cần tính trên một dòng.

Examples

Sample Input

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

Sample Output

12
7
6

Scoring

• Subtask ~1~ ~-~ ~500~ điểm: ~N,Q \le 3000~
• Subtask ~2~ ~-~ ~500~ điểm: Không có truy vấn loại ~1~
• Subtask ~3~ ~-~ ~750~ điểm: Không có truy vấn loại ~2~
• Subtask ~4~ ~-~ ~750~ điểm: Không có ràng buộc gì thêm