28424번 - 의리 게임

의리 게임이란 주어진 $X$ 리터의 술을 $1$번부터 $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$번 질의에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.