Cho dãy gồm ~n~ số nguyên ~𝑎_1,𝑎_2,...,𝑎_𝑛~. 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:

Thay phần tử thứ i của dãy bằng giá trị ~x~. Dịch dãy sang phải ~k~ vị trí, nếu dãy hiện tại là ~𝑎_1,𝑎_2,...,𝑎_𝑛~ thì sau khi dịch sẽ là: ~𝑎_{𝑛-𝑘+1},𝑎_{𝑛-𝑘+2}~,...,~𝑎_𝑛,𝑎_1,𝑎_2,...,𝑎_{𝑛-𝑘}~.

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 vào:

• Dòng thứ nhất ghi số nguyên dương ~n~ (~2 ≤ n ≤ 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 ~𝑎_1,𝑎_2,...,𝑎_𝑛~(~-10^9 ≤𝑎_𝑖≤ 10^9~ với ~𝑖=1,2,...,𝑛~).

• Dòng thứ ba ghi số nguyên dương ~q~ (~1≤𝑞≤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≤𝑖≤𝑛,-10^9≤𝑥≤10^9~)

• 2 k: là phép toán loại 2(~1≤𝑘<𝑛~).

Kết quả:

• 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 đó. Tự đảm bảo rằng kết quả thu được từ các phép toán loại 1 trong tệp dữ liệu vào không vượt quá 10^{18}.

Ràng buộc:

Có 20% số test tương ứng 20% số điểm của bài có ~2 ≤𝑛≤1000~ và chỉ gồm phép toán loại 1.

Có 40% số test khác tương ứng 40% số điểm của bài có ~2 ≤ n ≤ 1000~.

Thời gian thực hiện mỗi test không quá 0,3 giây.

Example:

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.