说明

时间限制：1 Sec 内存限制：256 MB 输入文件：delay.in 输出文件：delay.out

新年伊始，小明就想去坐电车旅行了。

下海市有 $N$ 个车站，从车站 $i$ 出发，在 $T_i$ 分钟之后，每分钟都会有一班前往车站 $i+1$ 的电车，车程为 3 分钟。

不过，由于是新年伊始，电车偶尔会发生延误。当发生延误时，从车站 $L_i$ 到车站 $R_i$ 区间内所有车站的首班电车（指该车站原本 $T_i$ 分钟时出发的电车）都会延迟 $D_i$ 分钟。

小明最初在车站 1，请在每次电车延误发生后，计算他到达车站 $N$ 的最短时间。

当前时刻设定为 0 分钟。

输入格式

第一行一个整数 $N$。

第二行 $N-1$ 个整数 $T_1,T_2,\ldots,T_{N-1}$。

第三个一个整数 $M$。

后续 $M$ 行，第 $i$ 行三个整数 $L_i,R_i,D_i$ 表示从车站 $L_i$ 到车站 $R_i$ 区间内所有车站的首班电车都会延迟 $D_i$ 分钟

输出格式

输出 $M$ 行，第 $i$ 行一个整数表示第 $i$ 次延误发生时，小明到达车站 $N$ 的最短时间。

样例

样例 1

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

32
32
32
32
39

样例说明：第 $1$ 次电车延误导致车站 $1$ 的首班车延迟 $5$ 分钟，此时到达车站 $N$ 的最短时间为 $32$ 分钟。

第 $2$ 次电车延误导致车站 $2$ 至车站 $3$ 的首班车延迟 $7$ 分钟，此时到达车站 $N$ 的最短时间为 $32$ 分钟。

第 $3$ 次电车延误导致车站 $5$ 至车站 $8$ 的首班车延迟 $5$ 分钟，此时到达车站 $N$ 的最短时间为 $32$ 分钟。

第 $4$ 次电车延误导致车站 $6$ 至车站 $9$ 的首班车延迟 $7$ 分钟，此时到达车站 $N$ 的最短时间为 $32$ 分钟。

第 $5$ 次电车延误导致车站 $1$ 至车站 $9$ 的首班车延迟 $7$ 分钟，此时到达车站 $N$ 的最短时间为 $39$ 分钟。

样例 2

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

1000000027
2000000027
3000000027
4000000027
5000000027

样例 3

10
0 76 78 64 100 95 10 98 46
5
5 6 61
9 9 38
8 8 28
1 9 87
4 4 66

176
176
176
263
263

数据范围

对于 25% 的数据，$N \le 100$，$M \le 100$。

对于 100% 的数据，$2 \le N \le 10^5$，$0 \le T_i \le 10^9$，$1 \le M \le 10^5$，$1 \le L_i \le R_i < N$，$1 \le D_i \le 10^9$。