문제

민재는 $N$ ($1 \le N \le 2 \cdot 10^5$)개의 양동이가 수직으로 쌓여 있는 장치를 만들었다. 위에서부터 $i$번째에 있는 양동이의 용량은 $a_i$ 리터이다 ($1 \le a_i \le 10^9$). 가장 위에 있는 양동이 위에는 수도꼭지가 있어, 매초 $1$리터의 우유를 첫 번째 양동이에 흘려보낸다. 또한, 가장 아래에 있는 $N$번 양동이 밑에는 커다란 수조가 하나 있다.

어떤 양동이가 우유로 가득 차는 시점을 $t$초라고 하면, $t+1$초가 시작될 때 이 양동이는 뒤집혀서 그 안에 든 우유를 모두 쏟아낸다. 만약 이 양동이가 마지막 양동이가 아니라면 아래에 있는 양동이로 우유를 쏟으며, 마지막 양동이라면 수조로 우유를 쏟는다. 양동이는 $t+1$초가 끝날 때 다시 원래대로 돌아와 비어 있는 상태로 다시 채워지기 시작한다.

양동이가 뒤집혀 있는 동안에는 우유를 받을 수 없다. 즉, 이 $1$초 동안 위에서 내려오는 모든 우유는 손실된다. 또한, 양동이에서 아래 양동이로 쏟아지는 우유의 양이 아래 양동이의 용량을 초과하는 경우, 그 초과분은 모두 손실된다.

민재는 다음의 쿼리 $Q$ ($1 \le Q \le 3 \cdot 10^5$)개를 처리하려고 한다. 각 쿼리는 세 정수 $i, v, t$로 주어진다.

먼저, $a_i = v$ ($1 \le i \le N, 1 \le v \le 10^9$)로 변경한다. 그 다음, 시각 $0$에 모든 양동이와 수조가 비어 있었다고 가정할 때, $t$초 ($1 \le t \le 10^{18}$)가 지난 후 수조에 담긴 우유의 총량을 구한다.

$a_i = v$로 변경된 값은 이후의 쿼리에서도 계속 유지된다.

입력

첫째 줄에 $N$이 주어진다.

둘째 줄에 $a_1, a_2, \dots, a_N$이 공백으로 구분되어 주어진다.

셋째 줄에 $Q$가 주어진다.

다음 $Q$개의 줄에는 각 쿼리를 나타내는 세 정수 $i, v, t$가 주어진다.

출력

각 쿼리에 대한 답을 한 줄에 하나씩 출력한다.

예제 입력 1

3
1 1 1
30
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 10

예제 출력 1

0
0
0
1
1
2
2
3
3
4
0
0
0
0
1
1
1
2
2
2
0
0
0
0
1
1
1
2
2
2

예제 입력 2

2
1 2
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10

예제 출력 2

0
0
0
0
2
2
2
2
4
4

예제 입력 3

3
1 1 1
1
1 1 1000000000000000000

예제 출력 3

499999999999999999

제한

• 테스트 케이스 4-5: $N \le 10, Q \le 100$, 모든 $t \le 10^4$
• 테스트 케이스 6-11: $N \le 10^3, Q \le 10^4$
• 테스트 케이스 12-23: 추가적인 제한 사항이 없다.