Dãy Bình Tràn

Có $n$ bình xếp theo thứ tự từ trên xuống dưới, đánh số $1$ đến $n$. Bình $i$ có dung tích $a_i$ và ban đầu rỗng.

Khi đổ nước vào bình $p$, bình đó nhận nước cho tới khi đầy. Phần nước vượt dung tích chảy toàn bộ sang bình $p+1$, rồi tiếp tục theo cùng quy tắc. Phần nước còn thừa sau bình $n$ bị mất.

Bạn cần xử lý các thao tác đổ nước và truy vấn lượng nước hiện có trong một bình.

Input

• Dòng đầu chứa $n$.
• Dòng tiếp theo chứa $n$ dung tích $a_1,\dots ,a_n$.
• Dòng tiếp theo chứa $m$.
• Mỗi truy vấn có dạng $1$ $p$ $x$ để đổ $x$ đơn vị nước vào bình $p$, hoặc $2$ $k$ để hỏi bình $k$.

Output

• Với mỗi truy vấn loại $2$, in lượng nước hiện có trong bình được hỏi.

Constraints

• $1\le n,m\le 2\cdot 10^5$.
• $1\le a_i\le 10^9$.
• Ở truy vấn loại $1$: $1\le p\le n$ và $1\le x\le 10^9$.
• Ở truy vấn loại $2$: $1\le k\le n$.
• Nước vượt khỏi bình $n$ bị mất; nước không bao giờ chảy ngược lên trên.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4
3 5 2 4
9
1 2 4
1 1 5
2 1
2 2
1 2 5
2 3
2 4
1 4 5
2 4

3
5
2
4
4