Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~. Xuất phát từ dãy ban đầu, ta thực hiện ~q~ lần một trong hai loại phép toán sau trên các dãy thu được.

1. Thay phần từ thứ ~i~ của dãy bằng giá trị ~x~.
2. Dịch dãy sang phải ~k~ vị trí, nếu dãy 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_n, a_1, a_2, ..., a_{n-k}~.

Yêu cầu

Sau mỗi lần thực hiện phép toán loại ~1~, hãy tính tổng giá trị các phần tử của dãy thu được.

Dữ liệu đầu vào

Gồm ~q + 3~ dòng:

• Dòng thứ nhất gồm số nguyên dương ~n~ ~(2 \le n \le 10^5)~;
• Dòng thứ hai ghi ~n~ số nguyên, các số ghi cách nhau dấu cách là giá trị của các số hạng của dãy ~a_1, a_2, ..., a_n~ ~(-10^9 \le a_i \le 10^9,\ i = 1, 2, ..., n)~;
• Dòng thứ ba ghi số nguyên dương ~q~ ~(1 \le q \le 10^5)~ là số phép toán cần thực hiện.
• ~q~ dòng tiếp theo, mỗi dòng mô tả một phép toán, các giá trị ghi cách nhau dấu cách:
  • ~1\ i\ x~: là phép toán loại ~1~ ~(1 \le i \le n,\ -10^9 \le x \le 10^9)~;
  • ~2\ k~: là phép toán loại ~2~ ~(1 \le k < n)~.

Dữ liệu đầu ra

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 các số hạng của dãy sau khi thực hiện phép toán, thứ tự các kết quả theo đúng thứ tự các phép toán loại ~1~ trong dữ liệu vào. Biết rằng kết quả không vượt quá ~10^{18}~.

Ràng buộc dữ liệu

• Có 20% số test tương ứng với 20% số điểm của bài có ~2 \le n \le 1000~ và chỉ gồm phép toán loại ~1~.
• Có 40% số test tương ứng với 40% số điểm của bài có ~2 \le n \le 1000~;
• Có 40% số test tương ứng với 40% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

4
4 1 2 5
4
2 2
1 2 7
2 1
1 3 -4

OUTPUT

14
3

Giải thích: Dãy ban đầu là: ~4, 1, 2, 5~.

• Sau phép toán thứ nhất ~(2\ 2)~, dãy mới sẽ là ~2, 5, 4, 1~.
• Sau phép toán thứ hai ~(1\ 2\ 7)~, dãy mới sẽ là ~2, 7, 4, 1~, có tổng bằng ~14~.
• Sau phép toán thứ ba ~(2\ 1)~ dãy mới sẽ là ~1, 2, 7, 4~.
• Sau phép toán thứ tư ~(1\ 3\ -4)~ dãy mới sẽ là ~1, 2, -4, 4~, có tổng bằng ~3~.