AT_pakencamp_2025_day2_c Pataro's Work

世界に羽ばたくイラストレーターであるパフィンのパ太郎は、たくさんの依頼にすべて誠実に応えることで有名である。 これからパ太郎のもとに依頼が入る。入る依頼は $ N $ 個で、 $ i $ 番目の依頼は時刻 $ T_i $ に入り、その報酬は $ P_i $ で、要求される完成度は $ Q_i $ である。不思議なことに、 $ P_i $ はすべて相異なる。 パ太郎は、時刻 $ 1,2,\dots $ の順に以下の行動を行う。 - まず、その時刻に入った依頼を確認する。はじめ、これらの依頼の進捗は $ 0 $ である。 - まだ終わっていない依頼があるなら、そのうち最も報酬が大きい依頼を選び、進捗を $ 1 $ 増やす。進捗が $ Q_i $ と等しくなった依頼は終わる。 スケジュールを練っているうちに、パ太郎は、知り合いであるK運営長が唐突に依頼を入れる可能性に気がついた。パ太郎は $ X $ 個のシナリオを考えている。 $ i $ 番目のシナリオは以下のようなものである。 - K運営長が、時刻 $ t_i $ に報酬 $ p_i $ 、要求される完成度 $ q_i $ の依頼を入れる。不思議なことに、 $ P $ に $ p_i $ は含まれない。 各シナリオについて、K運営長の依頼が終わる時刻を求めるプログラムを作成せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T_1 $ $ P_1 $ $ Q_1 $ $ T_2 $ $ P_2 $ $ Q_2 $ $ \vdots $ $ T_N $ $ P_N $ $ Q_N $ $ X $ $ t_1 $ $ p_1 $ $ q_1 $ $ t_2 $ $ p_2 $ $ q_2 $ $ \vdots $ $ t_X $ $ p_X $ $ q_X $

$ X $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のシナリオに対する答えを出力せよ。

### 小課題 1. ( $ 10 $ 点) $ X\leq 10 $ 2. ( $ 15 $ 点) $ P_i\gt P_{i+1} $ 3. ( $ 20 $ 点) $ T_i,t_i\leq 2\times 10^5,\sum_{i=1}^{N}Q_i\leq 2\times 10^5,q_i\leq 2\times 10^5 $ 4. ( $ 55 $ 点) 追加の制約はない。 ### Sample Explanation 1 報酬が $ p $ 、要求される完成度が $ q $ の依頼を依頼 $ (p,q) $ と表す。 $ 1 $ 番目のシナリオでは、パ太郎は以下のように行動する。 - 時刻 $ 1 $ に、依頼 $ (4,4),(8,2) $ が入る。報酬が最も高いのは依頼 $ (8,2) $ なので、依頼 $ (8,2) $ の進捗を $ 1 $ 増やす。 - 時刻 $ 2 $ に、依頼 $ (6,5),(9,2) $ が入る。報酬が最も高いのは依頼 $ (9,2) $ なので、依頼 $ (9,2) $ の進捗を $ 1 $ 増やす。 - 時刻 $ 3 $ に、依頼 $ (10,1) $ が入る。報酬が最も高いのは依頼 $ (10,1) $ なので、依頼 $ (10,1) $ の進捗を $ 1 $ 増やす。進捗が $ 1 $ になったので、この依頼は終わる。 - 時刻 $ 4 $ に、依頼 $ (2,1) $ が入る。報酬が最も高いのは依頼 $ (9,2) $ なので、依頼 $ (9,2) $ の進捗を $ 1 $ 増やす。進捗が $ 2 $ になったので、この依頼は終わる。 K運営長の依頼である依頼 $ (9,2) $ は時刻 $ 4 $ に終わるので、 $ 4 $ を出力せよ。 この入力は小課題 $ 1,3,4 $ の制約を満たす。 ### Sample Explanation 2 この入力は小課題 $ 2,4 $ の制約を満たす。 ### Constraints - $ 1 \leq N \leq 2\times 10^5 $ - $ 1\leq T_1\leq T_2\leq \dots \leq T_N\leq 10^{14} $ - $ 1\leq P_i\leq 10^9 $ - $ P_i\ne P_j $ $ (i\ne j) $ - $ 1\leq Q_i\leq 10^9 $ - $ 1\leq X\leq 2\times 10^5 $ - $ 1\leq t_i\leq 10^{14} $ - $ 1\leq p_i\leq 10^9 $ - $ p_i \ne P_j $ - $ 1\leq q_i\leq 10^9 $ - 入力はすべて整数