题目描述
Problem Description
Let's call the day counting from today as Day $ i $. For example, today is Day $ 1 $, and tomorrow is Day $ 2 $.
Mako-san has been assigned $ N $ homework assignments numbered from $ 1 $ to $ N $. She will start from Day $ 1 $ and complete one homework assignment per day. If she completes homework $ i $ on or before Day $ A_i $, she will get $ X_i $ points. If she completes it on or after Day $ (A_i+1) $, she will get $ Y_i $ points. Here, $ X_i > Y_i $.
Mako-san wants to know the maximum total score she can get by Day $ k $ for each $ k $ ($1 \leq k \leq N$). Please find this for her.
Input Format
The input is given from the standard input in the following format:
$ N $ $ A_1 $ $ X_1 $ $ Y_1 $ $ A_2 $ $ X_2 $ $ Y_2 $ $\vdots$ $ A_N $ $ X_N $ $ Y_N $
Output Format
Output $ N $ lines. The $ k $-th line should contain the maximum total score that can be obtained by Day $ k $.
Sample Input and Output
Sample Input #1
3
1 10 9
1 7 4
2 3 2
Sample Output #1
10
16
19
Sample Input #2
6
2 58 37
2 67 12
3 82 79
4 23 6
4 82 64
1 40 17
Sample Output #2
82
164
231
289
309
328
Sample Input #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
Sample Output #3
973186445
1911911518
2842686904
3679874527
4403933520
5125799158
5756526670
6376149728
6981973919
7253580890
7495545779
7554618966
7604240001
7639367940
7652179096
Notes/Hints
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq N$
- $1 \leq Y_i < X_i \leq 10^9$
- All input values are integers.
Sample Explanation 1
The optimal way to complete the homework for each $ k $ is as follows. For $ k=1 $, completing homework $ 1 $ on Day $ 1 $ gives $ 10 $ points. For $ k=2 $, completing homework $ 2 $ on Day $ 1 $ and homework $ 1 $ on Day $ 2 $ gives $ 7+9=16 $ points. For $ k=3 $, completing homework $ 2 $ on Day $ 1 $, homework $ 3 $ on Day $ 2 $, and homework $ 1 $ on Day $ 3 $ gives $ 7+3+9=19 $ points.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分