Truy vấn

View as PDF

Time limit: 3.0s , Memory limit: 512M , Points: 2500 (partial)

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 NQ (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

Comments