There are $N$ ($1\le N\le 2\cdot 10^5$) buckets in a stack where the $i$-th bucket from the top has capacity $a_i$ gallons ($1\le a_i\le 10^9$). A tap above the top bucket sends one gallon of milk per second into the first bucket per second. There is also a pool below bucket $N$.

When a bucket reaches its capacity after $t$ seconds, at the start of the $t+1$th second it flips to dump its contents into either the bucket below if it is not the last bucket or the pool otherwise (it reverts back to filling at the end of the $t+1$th second). A bucket cannot collect milk while it is flipped; any milk arriving at the bucket above during this second is lost. Additionally, any amount of milk exceeding the capacity of the bucket below is lost.

Handle $Q$ ($1\le Q\le 3\cdot 10^5$) queries, each specified by three integers $i$, $v$, and $t$:

1. First, set $a_i=v$ ($1\le i\le N, 1\le v \le 10^9$).
2. Then answer the following question: Suppose that at time $0$, all buckets as well as the pool are empty. Determine the number of gallons of milk in the pool after $t$ seconds ($1\le t\le 10^{18}$).

The $a_i=v$ updates persist through later queries.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$.

The second line contains $a_1\dots a_N$.

The next line contains $Q$.

Then the following $Q$ lines contain three integers $i$, $v$, and $t$. This means that you should set $a_i=v$ and then answer the question for $t$.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the answer to each question on a separate line.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

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

When $a=[1, 1, 1]$,

• Bucket $1$ flips at times $2,4,6,\dots$
• Bucket $2$ flips at times $3,5,7,\dots$
• Bucket $3$ flips at times $4,6,8,\dots$

When $a=[2, 1, 1]$,

• Bucket $1$ flips at times $3,6,9,\dots$
• Bucket $2$ flips at times $4,7,10,\dots$
• Bucket $3$ flips at times $5,8,11,\dots$

When $a=[2, 2, 1]$,

• Bucket $1$ flips at times $3,6,9,\dots$
• Bucket $2$ flips at times $4,7,10,\dots$
• Bucket $3$ flips at times $5,8,11,\dots$

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0
0
0
0
2
2
2
2
4
4

SAMPLE INPUT:

3
1 1 1
1
1 1 1000000000000000000

SAMPLE OUTPUT:

499999999999999999

SCORING:

• Inputs 4-5: $N \le 10, Q\le 100$, and all $t\le 10^4$
• Inputs 6-11: $N\le 10^3, Q\le 10^4$
• Inputs 12-23: No additional constraints.

Problem credits: Akshaj Arora