在单轨铁路上运行的列车只能在车站会车。假设有一对列车同时从相反方向出发，一列从始发站出发，另一列从终点站出发（即从相反方向的始发站出发）。很可能其中一列火车需要在沿途的某个车站等待另一列火车。为了尽量减少延误，列车会在使得等待时间最小化的车站会车。

我们已知每两个相邻车站之间的行驶时间，且双向行驶时间相同。遗憾的是，由于铁路沿线的施工，行驶时间会不断变化。给定初始行驶时间以及每次变更后受影响路段的更新行驶时间，请编写一个程序，计算在每次变更后，从铁路两端出发的一对列车可能的最短等待时间。

输入格式

第一行包含车站数量 $n$。第二行包含 $n - 1$ 个数字，对应相邻车站之间的初始行驶时间（第 $i$ 个数字是车站 $i$ 和 $i + 1$ 之间的行驶时间）。第三行包含变更次数 $k$。接下来有 $k$ 行，每行包含两个数字：第一个数字 $j \in [1, n - 1]$ 指定车站，第二个数字给出车站 $j$ 和 $j + 1$ 之间更新后的行驶时间。请注意，车站编号从 1 开始，而不是 0。

数据范围

• $2 \le n \le 200\,000$
• $0 \le k \le 200\,000$
• 所有行驶时间（初始值和更新值）均为 $[1, 10^6]$ 范围内的整数。

输出格式

输出 $n+1$ 行，其中第 $i$ 行包含经过 $i - 1$ 次变更后的最短可能等待时间（第一行对应没有任何变更的情况）。

样例

输入 1

6
20 70 40 10 50
2
4 80
2 30

输出 1

10
0
40

说明

起初，从相反方向出发的列车应在车站 3 会车。第一列火车到达该站需要 90 分钟，第二列火车到达该站需要 100 分钟；因此等待时间为 10 分钟。第一次变更后，最佳会车点变为车站 4。两列火车到达该站都需要 130 分钟，因此都不需要等待。第二次变更后，它们仍然在车站 4 会车。但这一次，先到达的火车需要等待 40 分钟。