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

• Dòng thứ nhất ghi số nguyên dương \(n\) \((2 \leq n \leq 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 \leq a_i \leq 10^9\) với \(i = 1, 2, ..., n)\)
• Dòng thứ ba ghi số nguyên dương \(q\) \((1 \leq q \leq 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 \leq i \leq n, -10^9 \leq x \leq 10^9)\)
• 2 k: là phép toán loại 2 \((1 \leq k \leq n)\)

Kết quả

Ghi 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 khi thực hiện phép toán, thứ tự các kết quả ghi ra theo đúng thứ tự các phép toán loại 1 trong tệp dữ liệu vào. Biết rằng kết quả không vượt quá \(10^{18}\).

Ràng buộc:

• Có 20% số test tương ứng với 20% số điểm của bài có \(2 \leq n \leq 1000\) và chỉ gồm phép toán loại 1.
• Có 40% số test khác tương ứng với 40% số điểm của bài có \(2 \leq n \leq 1000\)

Ví dụ:

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.