AT_past20_o 超過クエリ

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`.

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 $

Print $ Q $ lines. The $ i $ -th lines should contain the answer to the $ i $ -th query.

### Sample Explanation 1 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 `-1` should 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 $ . ### 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.