問題文

今日から数えて i 日目のことを Day i と呼ぶことにします。 例えば、今日は Day 1、明日は Day 2 です。

マコさんは、1 から N までの番号がついた N 個の宿題を課されています。 彼女は、Day 1 から始めて 1 日あたり 1 個の宿題を選んで終わらせます。 宿題 i を Day A_i またはそれ以前に終わらせると、彼女は X_i 点を得ます。 また、Day (A_i+1) またはそれ以降に終わらせると、Y_i 点を得ます。 ここで、X_i > Y_i です。

マコさんは、それぞれの k (1 \leq k \leq N) について、Day k までに得られる得点の総和の最大値を知りたいです。 彼女の代わりにこれを求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• 1 \leq Y_i < X_i \leq 10^9
• 入力される値はすべて整数である。

入力例 1

3
1 10 9
1 7 4
2 3 2

出力例 1

10
16
19

各 k における最適な宿題の終わらせ方は、以下のようになります。

k=1 の場合、Day 1 に宿題 1 を終わらせれば、10 点を得ます。

k=2 の場合、Day 1 に宿題 2 を、Day 2 に宿題 1 を終わらせれば、7+9=16 点を得ます。

k=3 の場合、Day 1 に宿題 2 を、Day 2 に宿題 3 を、Day 3 に宿題 1 を終わらせれば、7+3+9=19 点を得ます。

入力例 2

6
2 58 37
2 67 12
3 82 79
4 23 6
4 82 64
1 40 17

出力例 2

82
164
231
289
309
328

入力例 3

15
9 605824191 280849371
4 596581791 33288517
9 721865638 162970480
3 973186445 472655273
6 305716162 49621035
8 630727512 144854327
5 314582040 241964889
2 837187623 326231876
1 619623058 10421080
9 938725073 25997036
2 256037683 12811156
8 930775386 430074396
9 724058993 159628544
9 519111960 59073187
3 157350380 35127939

出力例 3

973186445
1911911518
2842686904
3679874527
4403933520
5125799158
5756526670
6376149728
6981973919
7253580890
7495545779
7554618966
7604240001
7639367940
7652179096