问题陈述
有一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N。最初,所有元素 A 是 0。时 i=1,2,\ldots,T,针对 A:
- 添加 V_i 到每个 A_{L_i},A_{L_i+1},\dots,和 A_{R_i}.
鉴于 Q 查询,按顺序处理。 i第查询描述如下。
- 给定整数 l_i,r_i,和 x_i,第一次打印 A_{l_i}+A_{l_i+1}+\dots+A_{r_i} 变为 x_i 或更大。如果 A_{l_i}+A_{l_i+1}+\dots+A_{r_i} 小于 x_i 时间 T,打印
-1.
约束
- 1\leq N\leq 10^5
- 1\leq T,Q\leq 10^5
- 1\leq L_i\leq R_i\leq N
- 1\leq V_i\leq 10^5
- 1\leq l_i\leq r_i\leq N
- 1\leq x_i\leq 10^{15}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N T Q L_1 R_1 V_1 L_2 R_2 V_2 \vdots L_T R_T V_T l_1 r_1 x_1 l_2 r_2 x_2 \vdots l_Q r_Q x_Q
输出
打印 Q 行。 i第行应包含以下问题的答案 i第一个查询。
示例输入 1
6 3 4 3 5 3 1 4 2 2 6 4 2 5 15 3 4 5 6 6 5 1 6 30
示例输出 1
2 1 -1 3
序列 A 转换如下:
- 时间 1: (0,0,3,3,3,0).
- 时间 2: (2,2,5,5,3,0).
- 时间 3: (2,6,9,9,7,4).
每个查询的答案如下。
- 查询 1:值 第一次或大于 A_2+A_3+A_4+A_5 变为 15 时间 2.
- 查询 2:值 第一次或大于 A_4+A_5 变为 5 时间 1.
- 查询 3:值
第一次或大于 A_6 时间 3 小于 5,所以
-1。 - 查询 4:值 第一次或大于 A_1+A_2+A_3+A_4+A_5+A_6 变为 30 时间 3.
示例输入 2
100 10 10 54 77 89179 3 23 9999 35 58 58890 38 66 74496 27 49 86313 12 59 86105 23 91 9688 55 74 55468 53 61 36846 4 46 25191 23 48 6659862 6 59 2233031 38 73 9618591 65 86 801679 20 73 3689737 2 19 1320865 27 100 13177888 27 65 762017 80 96 6436 35 66 7954927
示例输出 2
-1 4 9 1 4 -1 -1 1 7 6