Chia căn cập nhật

Bài toán này sẽ là nơi bắt đầu cho chuỗi ngày dài học hỏi và khám phá cái hay của thuật toán chia căn.

Bạn được cho một dãy \(a\) gồm \(n\) số nguyên, và có \(q\) thao tác cần thực hiện. Có 2 loại thao tác chính:

• \(1 \; l \; r \; v\): Với \(l \le i \le r \; , a[i] = v\).
• \(2 \; l \; r\): Yêu cầu tính tổng của đoạn \([l, r]\).

Yêu cầu: thực hiện các thao tác và in ra đáp án theo thứ tự truy vấn loại \(2\).

Input

Dòng đầu là \(2\) số nguyên \(n, q\): độ dài mảng và số truy vấn.

Dòng thứ hai là \(n\) phần tử của dãy \(a\).

Tiếp theo đó là \(q\) dòng mô tả các thao tác.

Giới hạn:

• \(1 \le l, r \le n\)
• \(a_i, v \le 10^7\)

Output

In ra đáp án theo thứ tự truy vấn.

Example

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

6
6
2

Scoring

• \(20\%\) số điểm có \(n, q \le 10^3\).
• \(80\%\) số điểm có \(n, q \le 10^5\)