問題文

世界に羽ばたくイラストレーターであるパフィンのパ太郎は、たくさんの依頼にすべて誠実に応えることで有名である。

これからパ太郎のもとに依頼が入る。入る依頼は 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運営長の依頼が終わる時刻を求めるプログラムを作成せよ。

制約

• 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
• 入力はすべて整数

小課題

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 点) 追加の制約はない。

入力例 1

5
1 4 4
1 8 2
2 6 5
3 10 1
4 2 1
3
2 9 2
1 15 10
3 1 1

出力例 1

4
10
14

報酬が 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 の制約を満たす。

入力例 2

15
19271058196 967824729 152036485
22712438628 910500852 981520310
140039456534 857077284 620411718
250480340689 769431650 298766521
251317817929 744280520 361324668
274195603603 715892722 480968805
344670306080 499774361 297846843
404902144817 419370025 285187325
520643152574 320064892 924193632
521915710072 249168130 628902494
543856067506 245532751 755031424
561032100177 239276621 713892371
710671228979 198319687 722757772
786820954868 164832983 69837030
946667800961 80707350 486834509
15
759622046068 88860862 423817262
86416230707 596982638 272961036
222135105453 623807668 225447688
987307024314 434140395 210989591
284114340148 853214705 836365490
935147463515 366719378 859904884
22078598728 490910900 362117198
519370635632 736444921 422952344
909241707938 29032918 112179585
687828700252 980166390 487330736
588669383658 735908347 528451855
828303497438 455644532 870392056
969530498200 491489928 888795971
436550659389 138264655 343910843
548244874878 118927479 759025737

出力例 2

760045863329
86689191742
222360553140
987518013904
284950705637
936007368398
22440715925
519793587975
909353887522
688316030987
589197835512
829173889493
970419294170
436894570231
549003900614

この入力は小課題 2,4 の制約を満たす。