콘서트

현빈이가 사는 도시에는 날마다 콘서트가 열린다.

현빈이는 소음에 민감해 $N$개의 방음벽을 설치하였다. 방음벽은 순서대로 $1$번부터 $N$번까지의 번호를 가지며, $i$번 방음벽은 $D\_i$만큼의 소음을 흡수할 수 있다. 방음벽을 설치한 뒤, 현빈이는 앞으로 모든 콘서트는 두 연속한 방음벽 사이에서만 열 수 있도록 규칙을 세웠다. 즉, 앞으로 모든 콘서트가 열리는 위치는 어떤 정수 $c$에 대해 $c$번 방음벽과 $c+1$번 방음벽 사이여야 한다. ($1\leq c\<N$)

모든 소음을 흡수해 조용한 나날을 보내려던 현빈이의 계획과 달리, 방음벽이 콘서트의 소음을 완전히 감당하지 못하는 일이 생기기도 했다. 예를 들어, $x$의 소음을 가진 콘서트가 $c$와 $c+1$번 방음벽 사이에서 열렸다고 하자. 이때 $c$번 방음벽이 흡수할 수 있는 소음은 $\min(D\_c,x)$뿐이고, 만약 흡수되지 못한 소음이 있다면 해당 소음은 $c-1$번 방음벽으로 향하게 된다. 마찬가지로, $c+1$번 방음벽 또한 $\min(D\_{c+1},x)$만큼의 소음만 흡수하고, 흡수되지 못한 소음은 $c+2$번 방음벽으로 향하게 된다. 이 과정은 더 이상 흡수될 소음이 없거나 소음을 흡수할 방음벽이 남아 있지 않을 때까지 반복된다.

현빈이는 매 콘서트가 끝난 직후, $N$개의 모든 방음벽에 대하여 각 방음벽이 흡수한 소음의 양만큼 방음벽을 보강할 것이다. 즉, 어떤 방음벽 $k$가 흡수한 소음이 $x$라면, 콘서트가 끝난 직후 $k$번 방음벽이 흡수할 수 있는 소음은 $D\_k+x$가 된다.

현빈이는 $Q$회에 걸쳐 아래 작업 중 하나를 진행한다.

• $1$ $c$ $x$: $c$와 $c+1$번 방음벽 사이에서 소음 $x$의 콘서트가 열려, 방음벽을 보강한다. ($1\leq c\<N$; $1\leq x\leq 10^9$)
• $2$ $c$: $c$번 방음벽이 흡수할 수 있는 소음의 크기를 측정한다. ($1\leq c\leq N$)

$2$번 작업을 진행할 때마다 주어진 방음벽이 흡수할 수 있는 소음을 빠르게 계산해 보자.

첫째 줄에 현빈이가 설치한 방음벽의 수 $N$이 주어진다. ($2\leq N \leq 200\\,000$)

둘째 줄에 $N$개의 방음벽이 흡수할 수 있는 소음의 크기 $D\_1, D\_2, \cdots, D\_N$이 공백으로 구분되어 주어진다. ($1\leq D\_i \leq 10^9$)

셋째 줄에 현빈이가 진행한 작업의 수 $Q$가 주어진다. ($1\leq Q \leq 200\\,000$)

이후 $Q$개의 줄에 걸쳐, 현빈이가 진행할 작업에 대한 정보가 지문과 같은 형식으로 주어진다. $2$번 작업이 최소 한 번 이상 주어짐이 보장된다.

입력으로 들어오는 모든 수는 정수이다.

$Q$개의 줄에 현빈이가 진행한 모든 $2$번 작업의 결과를 순서대로 출력한다.