Có \(n\) viên bi bố trí cách đều theo hàng ngang và được đánh số thứ tự từ \(1\) đến \(n\). Viên bi thứ \(i\) (\(1 \le i \le n\)) có độ đẹp là \(a_i\). Tiến hành thực hiện \(q\) lần một trong hai loại thao tác sau trên dãy các viên bi này:

• 1 i x: thay viên bi tại vị trí thứ \(i\) bằng một viên bi khác có độ đẹp \(x\) (\(1 \le i \le n\), \(-10^9 \le x \le 10^9\)).
• 2 k: dịch chuyển các viên bi sang phải \(k\) vị trí, nếu dãy các viên bi hiện tại là \(a_1, a_2, \dots, a_n\) thì sau khi dịch sẽ là \(a_{n-k+1}, a_{n-k+2}, \dots, a_n, a_1, a_2, \dots, a_{n-k}\) (\(1 \le k \le n\)).

Yêu cầu: sau mỗi lần thực hiện thao tác loại 1, hãy tính tổng độ đẹp của dãy các viên bi đang xuất hiện trên dãy.

Input

• Dòng thứ nhất chứa hai số nguyên \(n, q\) (\(1 \le n, q \le 5\cdot 10^5\)) cách nhau một khoảng trắng.
• Dòng thứ hai chứa các số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)) lần lượt là độ đẹp của các viên bi, các số cách nhau một khoảng trắng.
• \(q\) dòng tiếp theo, mỗi dòng mô tả một thao tác trên, các số cách nhau một khoảng trắng.

Output

• Tương ứng với mỗi phép toán loại 1 ghi ra một số nguyên trên một dòng là tổng độ đẹp của dãy các viên bi xuất hiện trên dãy, thứ tự các kết quả theo đúng thứ tự các phép toán loại 1 trong tệp dữ liệu đầu vào.

Scoring

• Có \(40\%\) số test đầu với \(2 \le n \le 1000\) và chỉ gồm thao tác loại 1.
• Có \(30\%\) số test tiếp theo với \(2 \le n \le 1000\).
• Có \(30\%\) số test còn lại không giới hạn gì thêm.

Example

4 4
5 3 2 7
2 2
1 3 8
2 1
1 2 -6

20
12