B. Магазин целых чисел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Магазин целых чисел продаёт $$$n$$$ отрезков, $$$i$$$-й из которых состоит из чисел от $$$l_i$$$ до $$$r_i$$$ и стоит $$$c_i$$$ монет.

Завтра Вася отравится в этот магазин и купит несколько отрезков. Он получит все числа, лежащие хотя бы в одном из выбранных отрезков. Количество монет, которое он потратит на покупку равно сумме стоимостей отрезков, которые он купит.

В качестве подарка за покупку, Вася дополнительно получит ещё несколько целых чисел. Число $$$x$$$, не купленное Васей ранее, он получит тогда и только тогда, когда для $$$x$$$ выполняются два следующих условия:

  • Найдётся купленное Васей число $$$l$$$, меньшее $$$x$$$.
  • Найдётся купленное Васей число $$$r$$$, большее $$$x$$$.

Число $$$x$$$ Вася может получить в подарок не более одного раза, таким образом все числа, которые получит Вася будут различными.

Например, если Вася купит отрезок $$$[2, 4]$$$ за $$$20$$$ монет и отрезок $$$[7, 8]$$$ за $$$22$$$ монеты, он потратит $$$42$$$ монеты и получит числа $$$2, 3, 4, 7, 8$$$ как содержимое отрезков. В качестве подарка он получит числа $$$5$$$ и $$$6$$$.

По техническим причинам, завтра в магазине будут доступны к покупке только $$$s$$$ первых отрезков (то есть отрезки $$$[l_1, r_1], [l_2, r_2], \ldots, [l_s, r_s]$$$). Вася не сможет купить отрезки, не доступные к покупке.

Вася хочет получить (купить или получить в подарок) как можно больше целых чисел. Если это можно сделать разными способами, то он выберет самый дешёвый из них.

Для всех значений $$$s$$$ от $$$1$$$ до $$$n$$$ определите, сколько монет потратит Вася, если к покупке будут доступны только $$$s$$$ первых отрезков.

Входные данные

В первой строке задано одно целое число $$$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$$$) из них должно быть равно количеству монет, которое потратит Вася, если к покупке будут доступны только первые $$$s$$$ отрезков.

Пример
Входные данные
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
Выходные данные
20
42
42
42
4
13
11
256
271
271
Примечание

В первом наборе входных данных при $$$s = 1$$$ Вася может купить только один отрезок $$$[2, 4]$$$ за $$$20$$$ монет и получить $$$3$$$ числа.

Способ получить $$$7$$$ чисел за $$$42$$$ монеты при $$$s = 2$$$ описан в условии.

Во втором наборе входных данных обратите внимание на то, что в магазине могут быть одинаковые отрезки.