問題文

新年早々Noelちゃんは電車で旅行に出かけたくなりました.
霧弥湖町にはN個の駅があります, $駅_i$からは$T_i$分以降1分ごとに$駅_{i+1}$まで3分で向かう電車が出ています.
ただし新年早々ゆえに電車遅延が時々発生します, 電車遅延が起こると$駅_{L_i}$から$駅_{R_i}$までの始発電車が$D_i$分遅れます.
Noelちゃんは初め駅1にいます, 電車遅延が起こるたびにNoelちゃんが駅$N$に着く最短時間を求めてください.

現在時刻は$0$とします。

入力

$N$
$T_1\ T_2\ \cdots \ T_{N-1}$
$M$
$L_1\ R_1\ D_1$
$L_2\ R_2\ D_2$
$\vdots$
$L_{M-1}\ R_{M-1}\ D_{M-1}$
$L_M\ R_M\ D_M$

1行目に駅の個数$N(2\le N\le 10^5)$が与えられます.
2行目に$N-1$個の駅の始発電車の時刻$T_i(0\le T_i\le 10^9)$が整数で与えられます.
3行目に電車遅延の回数$M(1\le M\le 10^5)$が与えられます.
4行目から4+M行目までに電車遅延の範囲$L_i, R_i(1\le L_i\le R_i< N)$と遅延時間$D_i(1\le D_i\le 10^9)$が整数で与えられます.

出力

M行の出力があります, 各行には対応する電車遅延発生後のNoelちゃんの必要時間を整数で改行付きで出力してください.

サンプル

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

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

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