题目描述

在一个堆栈中有 $N$ ($1\le N\le 2\cdot 10^5$) 个桶，从顶部开始数第 $i$ 个桶的容量为 $a_i$ 加仑 ($1\le a_i\le 10^9$)。顶部桶上方有一个水龙头，每秒向第一个桶注入一加仑牛奶。在第 $N$ 个桶下方还有一个水池。

当一个桶在 $t$ 秒后达到其容量时，在第 $t+1$ 秒开始时，它会翻转，将其内容物倒入下方的桶中（如果不是最后一个桶）或倒入水池中（它会在第 $t+1$ 秒结束时恢复为接收状态）。桶在翻转时无法收集牛奶；在此期间到达上方桶的任何牛奶都会丢失。此外，任何超过下方桶容量的牛奶也会丢失。

处理 $Q$ ($1\le Q\le 3\cdot 10^5$) 次查询，每次查询由三个整数 $i$、$v$ 和 $t$ 指定：

1. 首先，设置 $a_i=v$ ($1\le i\le N, 1\le v \le 10^9$)。
2. 然后回答以下问题：假设在时间 $0$ 时，所有桶以及水池都是空的。确定 $t$ 秒后水池中有多少加仑牛奶 ($1\le t\le 10^{18}$)。

$a_i=v$ 的更新在后续查询中持续有效。

输入格式

第一行包含 $N$。

第二行包含 $a_1\dots a_N$。

下一行包含 $Q$。

接下来的 $Q$ 行，每行包含三个整数 $i$、$v$ 和 $t$。这意味着你需要设置 $a_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

说明 1

当 $a=[1, 1, 1]$ 时，

• 桶 $1$ 在时间 $2,4,6,\dots$ 翻转
• 桶 $2$ 在时间 $3,5,7,\dots$ 翻转
• 桶 $3$ 在时间 $4,6,8,\dots$ 翻转

当 $a=[2, 1, 1]$ 时，

• 桶 $1$ 在时间 $3,6,9,\dots$ 翻转
• 桶 $2$ 在时间 $4,7,10,\dots$ 翻转
• 桶 $3$ 在时间 $5,8,11,\dots$ 翻转

当 $a=[2, 2, 1]$ 时，

• 桶 $1$ 在时间 $3,6,9,\dots$ 翻转
• 桶 $2$ 在时间 $4,7,10,\dots$ 翻转
• 桶 $3$ 在时间 $5,8,11,\dots$ 翻转

样例输入 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：无额外限制。

题目来源：Akshaj Arora