配点 : 1500 点
問題文
从今天开始算 i 日 我们称之为 i 。 例如,今天是 Day 1明天是白天 2 。
真子桑, 编号至1 减去 N 包含 N 家庭作业。 她是日 从 1 开始 1 每天 选择并完成 1 家庭作业。 作业 i 天 A_i 或更早,她会 获得 X_i 分。 还有,日 如果您在 (A_i+1) 或之后完成, 获得Y_i 分。 在这里,X_i > Y_i 。
真子桑有每个 k (1 \leq k \leq N) 关于日 我想知道 k 可以获得的最高总分。 代表她提出这个要求。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq Y_i < X_i \leq 10^9
- 所有输入值都是整数。 如果您想走
入力
输入是按以下格式从标准输入给出的。
N A_1 X_1 Y_1 A_2 X_2 Y_2 \vdots A_N X_N Y_N
出力
N 行。 k 这一天 打印到 k 为止获得的总分的最大值。
入力例 1
3 1 10 9 1 7 4 2 3 2
出力例 1
10 16 19
各 k 作业的最佳方式如下。 如果
k=1 ,日 关于 1 的家庭作业 如果你完成了 1 , 获得10 分。
k=2 ,日 关于 1 的家庭作业 如果你完成了 2 ,日 2 的家庭作业 如果你完成了 1 , 获得7+9=16 分。
k=3 ,日 关于 1 的家庭作业 如果你完成了 2 ,日 2 的家庭作业 如果你完成了 3 ,日 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