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 cuyể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, ..., a_n~ thì sau khi dịch sẽ là dãy ~a_{n-k+1}, a_{n-k+2}, ..., a_1, a_2, ..., a_{n-k}(1 \le k \le n)~

Yêu cầu

Sau khi 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

Đọc từ tệp văn bản DODEP.INP có cấu trúc như sau:

• Dòng thứ nhất chứa hai số nguyên dương ~n, q(1 \le n, q \le 5.10^5)~ cách nhau một khoản trắng.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., 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ản 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ản trắng.

Output

Tương ứng với mỗi phép toán loại ~1~ ghi ra tệp văn bản DODEP.OUT 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.

Ví dụ

DODEP.INP

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

DODEP.OUT

20
12

Giải thích

Dãy ban đầu 5 3 2 7
Sau phép toán thứ nhất (2 2) dãy mới sẽ là 2 7 5 3
Sau phép toán thứ hai (1 3 8) dãy mới sẽ là 2 7 8 3, có tổng bằng 20
Sau phép toán thứ ba (2 1) dãy mới sẽ là 3 2 7 8
Sau phép toán thứ tư (1 2 -6) dãy mới sẽ là 3 -6 7 8, có tổng bằng 12

Ràng buộc

• 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