問題文

モリタ君はプログラミングコンテストの商品として長さ N の数列 a_1, a_2, ..., a_N を貰いました。

まず、この数列に対し A 個の加算クエリを行います。i 個目の加算クエリは以下のとおりです。

• L_i, R_i, X_i が与えられるので、a_{L_i}, a_{L_i+1}, ..., a_{R_i} それぞれに X_i を足す

そのあと、B 個の調査クエリを行います。この調査クエリの結果を求めるのがあなたの仕事です。i 個目の調査クエリは以下のとおりです。

• S_i, T_i, K_i が与えられるので、S_i 個目の加算クエリを行う直前から、T_i 個目の加算クエリを行った直後までの間での a_{K_i} の最小値を求める

制約

• 1 ≦ N ≦ 10^5
• 1 ≦ A, B ≦ 10^5
• |a_i| ≦ 10^6
• 1 ≦ L_i ≦ R_i ≦ N
• |X_i| ≦ 10^6
• 1 ≦ S_i ≦ T_i ≦ A
• 1 ≦ K_i ≦ N

入力例 1

3
0 1 2
3
1 2 10
1 3 -20
2 3 20
6
1 1 1
1 2 1
3 3 2
1 1 2
1 1 3
1 3 3

出力例 1

0
-10
-9
1
2
-18

数列は以下のように変動します

• [0, 1, 2] : 最初
• [10, 11, 2] : 1つめのクエリの後
• [-10, -9, -18] : 2つめのクエリの後
• [-10, 11, 2] : 3つめのクエリの後

調査クエリの出力は以下のとおりです

• 1つめの調査クエリはmin(0, 10)=0を出力します
• 2つめの調査クエリはmin(0, 10, -10)=-10(21:18修正)を出力します
• 3つめの調査クエリはmin(-9, 11)=-9を出力します
• 4つめの調査クエリはmin(1, 11)=1を出力します
• 5つめの調査クエリはmin(2, 2)=2を出力します
• 6つめの調査クエリはmin(2, 2, -18, 2)=-18を出力します

入力例 2

3
454314 -698320 390858
7
1 3 -916798
1 2 -927828
2 2 537269
1 1 -765412
3 3 -299727
3 3 250850
3 3 526409
7
3 5 3
1 5 1
7 7 1
6 6 1
4 5 3
3 6 3
6 6 2

出力例 2

-825667
-2155724
-2155724
-2155724
-825667
-825667
-2005677

入力例 3

7
74567 -876079 911351 746764 -924924 713268 666931
7
6 7 -318557
5 6 -349441
2 4 -629716
3 7 595329
4 7 174594
5 5 -948318
2 6 -47210
8
2 4 4
1 5 3
3 5 5
1 3 3
4 7 5
1 7 1
5 5 5
6 7 2

出力例 3

117048
281635
-1274365
281635
-1499970
74567
-679036
-1553005