의리 게임

의리 게임은 $X$ 리터의 술을 1번부터 $N$번까지 번호가 붙은 학생 $N$명이 차례대로 모두 마시는 게임이다. 다행히 항공대학교 학생들은 모두 의리가 넘쳐서, 자신에게 넘어온 술은 최대 주량까지 마시려고 노력한다.

여기서 최대 주량은 한 사람이 마실 수 있는 술의 최대량을 뜻한다. 술을 최대 주량까지 모두 마시면 만취 상태가 되고, 그때부터는 의리를 잊고 다음 번호 학생에게 술을 바로 넘긴다. 단, 마지막 차례인 $N$번 학생에게 술이 왔을 때 술을 마시다 만취 상태가 되거나 이미 만취 상태라면 술을 모두 버린다.

다음과 같은 두 가지 질의가 시간 순서대로 주어진다. 이 질의들은 누적된다.

• 1 $i$ $x$: $i$번 사람이 $x$ 리터의 술을 가지고 $i$번 사람부터 $N$번 사람까지 의리 게임을 진행한다. ($1 \leq i \leq N$; $1 \leq x \leq 1\,000\,000\,000$)
• 2 $i$: 지금까지 $i$번 학생이 마신 술의 양을 출력한다. ($1 \leq i \leq N$)

첫째 줄에 학생 수 $N$과 질의 수 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N, Q \leq 100\,000$)

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번 학생의 최대 주량 $m_i$가 주어진다. ($1 \leq m_i \leq 10^9$; $1 \leq i \leq N$)

$N + 2$번째 줄부터 $Q$개의 줄에 걸쳐 각 질의가 위에서 설명한 형식대로 주어진다.

주어지는 수는 모두 정수이다.

2번 질의(지금까지 마신 술의 양을 묻는 질의)에 대한 답을 한 줄에 하나씩 순서대로 출력한다.