Cho dãy ~n~ số nguyên ~a_1, a_2, \ldots, a_n~. Thực hiện ~q~ phép toán thuộc một trong hai loại:

• 1 i x: thay phần tử thứ ~i~ của dãy hiện tại bằng ~x~.
• 2 k: dịch dãy sang phải ~k~ vị trí.

Yêu cầu: Sau mỗi phép toán loại 1, in tổng các phần tử của dãy hiện tại.

Input

Đọc từ file văn bản CAU4.INP:

• Dòng đầu tiên ghi ~n~ (~2 \le n \le 10^5~).
• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~-10^9 \le a_i \le 10^9~).
• Dòng thứ ba ghi ~q~ (~1 \le q \le 10^5~).
• ~q~ dòng tiếp theo mô tả các phép toán theo định dạng trên.

Output

Ghi ra file văn bản CAU4.OUT; với mỗi phép toán loại 1, ghi tổng các phần tử của dãy sau khi thực hiện phép toán đó trên một dòng. Kết quả không vượt quá ~10^{18}~.

Scoring

• Subtask ~1~ ~(20\%)~: ~n \le 1000~ và chỉ gồm phép toán loại 1.
• Subtask ~2~ ~(40\%)~: ~n \le 1000~.
• Subtask ~3~ ~(40\%)~: không có ràng buộc gì thêm.

Example input 1

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

Example output 1

14
3