AT_past20_o 超過クエリ

長さ $ 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` を出力する。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 数列 $ 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 $ です。 ### 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} $ - 入力は全て整数