Problem Description

Morita received a sequence of length $ N $, $a_1,\ a_2,\ ...,\ a_N$, as a prize in a programming contest.

First, $ A $ addition queries will be performed on this sequence. The $ i $-th addition query is as follows:

• Given $L_i,\ R_i,\ X_i$, add $ X_i $ to each of $a_{L_i},\ a_{L_i+1},\ ...,\ a_{R_i}$

After that, $ B $ investigation queries will be performed. Your task is to determine the results of these investigation queries. The $ i $-th investigation query is as follows:

• Given $S_i,\ T_i,\ K_i$, find the minimum value of $ a_{K_i} $ from just before the $ S_i $-th addition query to just after the $ T_i $-th addition query

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ ... $ a_N $ $ A $ $ L_1 $ $ R_1 $ $ X_1 $ $ L_2 $ $ R_2 $ $ X_2 $ : $ L_A $ $ R_A $ $ X_A $ $ B $ $ S_1 $ $ T_1 $ $ K_1 $ $ S_2 $ $ T_2 $ $ K_2 $ : $ S_B $ $ T_B $ $ K_B $

Output Format

Output $ B $ lines. The $ i $-th line should contain the result of the $ i $-th investigation query. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #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

Sample Output #1

0
-10
-9
1
2
-18

Sample Input #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

Sample Output #2

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

Sample Input #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

Sample Output #3

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

Notes/Hints

Constraints

• $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$

Sample Explanation 1

The sequence fluctuates as follows:
- \[0, 1, 2\]: Initially
- \[10, 11, 2\]: After the first query
- \[-10, -9, -18\]: After the second query
- \[-10, 11, 2\]: After the third query

The output for the investigation queries is as follows:
- The first investigation query outputs min(0, 10)=0
- The second investigation query outputs min(0, 10, -10)=-10
- The third investigation query outputs min(-9, 11)=-9
- The fourth investigation query outputs min(1, 11)=1
- The fifth investigation query outputs min(2, 2)=2
- The sixth investigation query outputs min(2, 2, -18, 2)=-18

见题面 Input 部分

见题面 Output 部分