흘러넘치는 분수

지난주 Bill은 처음으로 샴페인 분수를 채웠다. 한 잔에서 다른 잔으로 샴페인이 쏟아지는 모습에 즐거워진 그는 다음 World Finals에서 더 큰 샴페인 분수를 만들기로 했다. 그는 이미 용량이 서로 다른 유리 그릇 $n$개를 주문했고, 이를 위아래로 쌓아 거대한 유리 분수를 만들 계획이다. 하지만 샴페인을 어떻게 부어야 할지는 아직 정하지 못했다. 한 병으로는 부족하고, 위에서만 부으면 모든 그릇이 채워지지 않을 수도 있다. Bill은 분수를 채우는 여러 방법을 시험해 보고 싶지만, 샴페인을 낭비하는 것은 아까운 일이다.

$i$번째 그림은 $i$번째 '+' 유형 쿼리를 시각화한 것이다.

당신의 과제는 주어진 분수에 샴페인을 붓는 과정을 시뮬레이션하는 프로그램을 작성하는 것이다. 어떤 레벨의 그릇이 이미 가득 차 있으면, 샴페인은 그 아래 레벨 중 용량이 더 큰 첫 번째 레벨로 넘쳐흐른다. 그 레벨도 가득 차 있으면 샴페인은 더 아래로 흘러 내려가고, 결국 땅에 스며들어 사라진다. Bill은 시뮬레이션 도중 특정 시점에 어떤 레벨에 샴페인이 얼마나 남아 있는지도 알고 싶어 한다.

첫 줄에는 레벨 수 $n$과 쿼리 수 $q$가 주어진다 ($1\leq n, q \leq 3 \cdot 10^5$).

둘째 줄에는 각 레벨의 용량을 리터 단위로 나타낸 서로 다른 정수 $n$개 $c$가 위에서 아래 순서로 주어진다 ($1\leq c \leq 10^9$).

이어지는 $q$개의 줄은 각각 쿼리를 나타낸다. 첫 기호 $t$는 '+' 또는 '?'이다.

• $t$가 '+'이면, 정수 $\ell$과 $x$가 주어진다 ($1 \leq \ell \leq n$, $1 \leq x \leq 10^9$). Bill은 레벨 $\ell$에 $x$리터의 샴페인을 붓는다.
• $t$가 '?'이면, 정수 $\ell$이 주어진다 ($1 \leq \ell \leq n$). Bill은 레벨 $\ell$에 현재 들어 있는 샴페인의 양(리터)을 묻는다.

적어도 하나의 '?' 유형 쿼리가 있음이 보장된다.

'?' 유형의 각 쿼리에 대해, 요청된 레벨에 현재 들어 있는 샴페인의 양을 리터 단위로 출력한다.