Độ đẹp

Có \(n\) viên bi bố trí cách đều thành 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, \ldots, a_n\) thì sau khi dịch sẽ là dãy \(a_{n-k+1}, a_{n-k+2}, \ldots, a_n, a_1, a_2, \ldots, 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 dương \(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 \(n\) số nguyên \(a_1, a_2, \ldots, 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 như trên, các số cách nhau một khoảng trắng.

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.

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ả đúng thứ tự các phép toán loại \(1\) trong dữ liệu đầu vào.

Example

Input:

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

Output:

20
12

Note

Dãy ban đầu: \(5\ 3\ 2\ 7\).

Sau phép toán thứ nhất (2 2) dãy mới là \(2\ 7\ 5\ 3\).

Sau phép toán thứ hai (1 3 8) dãy mới là \(2\ 7\ 8\ 3\), có tổng bằng \(20\).

Sau phép toán thứ ba (2 1) dãy mới là \(3\ 2\ 7\ 8\).

Sau phép toán thứ tư (1 2 -6) dãy mới là \(3\ {-6}\ 7\ 8\), có tổng bằng \(12\).