/ 
Time Limit: 10 sec / Memory Limit: 1024 MiB
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) があります。はじめ A の各要素は 0 です。時刻 i=1,2,\ldots,T において、A に対して以下の操作が行われます。
- A_{L_i},A_{L_i+1},\dots,A_{R_i} にそれぞれ V_i を加える
Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。
- 整数 l_i,r_i,x_i が与えられる。A_{l_i}+A_{l_i+1}+\dots+A_{r_i} が x_i 以上になる最初の時刻を出力する。ただし、時刻 T における A_{l_i}+A_{l_i+1}+\dots+A_{r_i} が x_i 未満のときは
-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：時刻 3 における A_6 の値が 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
Problem Statement
There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Initially, all elements of A are 0. At time i=1,2,\ldots,T, the following operation is performed against A:
- add V_i to each of A_{L_i},A_{L_i+1},\dots, and A_{R_i}.
Given Q queries, process them in order. The i-th query is described as follows.
- Given integers l_i,r_i, and x_i, print the first time that A_{l_i}+A_{l_i+1}+\dots+A_{r_i} becomes x_i or greater. If A_{l_i}+A_{l_i+1}+\dots+A_{r_i} is less than x_i at time T, print
-1.
Constraints
- 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}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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
Output
Print Q lines. The i-th lines should contain the answer to the i-th query.
Sample Input 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
Sample Output 1
2 1 -1 3
The sequence A transitions as follows:
- Time 1: (0,0,3,3,3,0).
- Time 2: (2,2,5,5,3,0).
- Time 3: (2,6,9,9,7,4).
The answer to each query is as follows.
- Query 1: the value A_2+A_3+A_4+A_5 becomes 15 or greater for the first time at time 2.
- Query 2: the value A_4+A_5 becomes 5 or greater for the first time at time 1.
- Query 3: the value A_6 at time 3 is less than 5, so
-1should be printed. - Query 4: the value A_1+A_2+A_3+A_4+A_5+A_6 becomes 30 or greater for the first time at time 3.
Sample Input 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
Sample Output 2
-1 4 9 1 4 -1 -1 1 7 6