← 返回题目列表

Codeforces · 1621/B

B. 整数商店

中文机器翻译题面 查看原题

整数商店出售 $$$n$$$ 段。其中第 $$$i$$$ 包含从 $$$l_i$$$ 到 $$$r_i$$$ 的所有整数,并花费 $$$c_i$$$ 硬币。

明天 Vasya 会去这家商店并在那里购买一些片段。他将获得至少出现在购买的一个段中的所有整数。采购总成本是采购中所有环节成本的总和。

购物后,Vasya将获得更多整数作为礼物。当且仅当满足以下所有条件时,他才会获得整数 $$$x$$$ 作为礼物:

- Vasya 尚未购买 $$$x$$$。
- Vasya 购买了小于 $$$x$$$ 的整数 $$$l$$$。
- Vasya 购买了大于 $$$x$$$ 的整数 $$$r$$$。

Vasya 只能获得一次整数 $$$x$$$ 作为礼物,因此他在收到礼物后不会拥有相同的整数。

例如,如果 Vasya 以 $$$20$$$ 硬币购买段 $$$[2, 4]$$$,并以 $$$22$$$ 硬币购买段 $$$[7, 8]$$$,则他花费 $$$42$$$ 硬币并从这些段接收整数 $$$2, 3, 4, 7, 8$$$。他还得到整数 $$$5$$$ 和 $$$6$$$ 作为礼物。

由于技术问题,明天商店中仅提供前 $$$s$$$ 段(即段 $$$[l_1, r_1], [l_2, r_2], \ldots, [l_s, r_s]$$$)。

Vasya 想要获得(购买或作为礼物获得)尽可能多的整数。如果他可以通过不同的方式做到这一点,他会选择其中最便宜的。

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$s$$$,找出如果只有前 $$$s$$$ 段可用,Vasya 将花费多少硬币。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含单个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 商店中的段数。

接下来的 $$$n$$$ 行包含三个整数 $$$l_i$$$、$$$r_i$$$、$$$c_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9, 1 \leq c_i \leq 10^9$$$) — 第 $$$i$$$ 段的末尾及其成本。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例输出 $$$n$$$ 整数:其中的第 $$$s$$$ ($$$1 \leq s \leq n$$$) 应该是 Vasia 在商店中花费的硬币数量(如果只有前 $$$s$$$ 段可用)。

示例

输入 #1

3
2
2 4 20
7 8 22
2
5 11 42
5 11 42
6
1 4 4
5 8 9
7 8 7
2 10 252
1 11 271
1 10 1

输出 #1

20
42
42
42
4
13
11
256
271
271

注意

在第一个测试用例中,如果 $$$s = 1$$$,则 Vasya 只能用 $$$20$$$ 硬币购买 $$$[2, 4]$$$ 段并获得 $$$3$$$ 整数。

语句中描述了在 $$$s = 2$$$ 的情况下获得 $$$42$$$ 硬币的 $$$7$$$ 整数的方法。

在第二个测试用例中请注意,商店中可以存在相同的段。