配点 : 900 点
問題文
森田君长期作为编程竞赛产品 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
入力
输入是按以下格式从标准输入给出的。
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
出力
B 行。 i 在线 来自 i 输出调查查询的结果。 在输出末尾插入换行符。
入力例 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] :第一次查询后
- [-10, -9, -18] : 第二次查询后
- [-10, 11, 2] :第三次查询后
研究查询的输出如下
- 第一个探测查询输出 min(0, 10)=0
- 第二个探测查询是 min(0, 10, -10)=-10 输出(21:18修正)将输出
- 第三个探测查询输出 min(-9, 11)=-9
- 第四个探测查询输出 min(1, 11)=1
- 第五次探测查询输出 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