B. Integers Shop-Hello 2022

Problem - 1621B - Codeforces

B. Integers Shop

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The integers shop sells nn segments. The ii-th of them contains all integers from lili to riri and costs cici coins.

Tomorrow Vasya will go to this shop and will buy some segments there. He will get all integers that appear in at least one of bought segments. The total cost of the purchase is the sum of costs of all segments in it.

After shopping, Vasya will get some more integers as a gift. He will get integer xx as a gift if and only if all of the following conditions are satisfied:

• Vasya hasn't bought xx.
• Vasya has bought integer ll that is less than xx.
• Vasya has bought integer rr that is greater than xx.

Vasya can get integer xx as a gift only once so he won't have the same integers after receiving a gift.

For example, if Vasya buys segment [2,4][2,4] for 2020 coins and segment [7,8][7,8] for 2222 coins, he spends 4242 coins and receives integers 2,3,4,7,82,3,4,7,8 from these segments. He also gets integers 55 and 66 as a gift.

Due to the technical issues only the first ss segments (that is, segments [l1,r1],[l2,r2],…,[ls,rs][l1,r1],[l2,r2],…,[ls,rs]) will be available tomorrow in the shop.

Vasya wants to get (to buy or to get as a gift) as many integers as possible. If he can do this in differents ways, he selects the cheapest of them.

For each ss from 11 to nn, find how many coins will Vasya spend if only the first ss segments will be available.

Input

The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains the single integer nn (1≤n≤1051≤n≤105) — the number of segments in the shop.

Each of next nn lines contains three integers lili, riri, cici (1≤li≤ri≤109,1≤ci≤1091≤li≤ri≤109,1≤ci≤109) — the ends of the ii-th segments and its cost.

It is guaranteed that the total sum of nn over all test cases doesn't exceed 2⋅1052⋅105.

Output

For each test case output nn integers: the ss-th (1≤s≤n1≤s≤n) of them should be the number of coins Vasia will spend in the shop if only the first ss segments will be available.

Example

input

Copy

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

output

Copy

20
42
42
42
4
13
11
256
271
271

Note

In the first test case if s=1s=1 then Vasya can buy only the segment [2,4][2,4] for 2020 coins and get 33 integers.

The way to get 77 integers for 4242 coins in case s=2s=2 is described in the statement.

In the second test case note, that there can be the same segments in the shop.

=========================================================================

首先要保证数字最多时，两段的数字是必须选的，而且不选不可，且选完之后内部就无须再选，所以我们维护left,right的极值。一旦能够修改，立马修改left,以及其花费，并且连同答案要一块修改。如果left和当前相同，则取最小值，连同答案一起修改。

特殊情况是，我们当前遇见的就是最大区间，则我们也要修改左右花费，但是我们把答案修改成本次单次花费和其本身的最小值即可。

# include<iostream>
# include<algorithm>
# include<math.h>
using namespace std;
typedef long long int ll;

ll lef[200000+10],righ[200000+10],cost[200000+10];


int main()
{


    /*
        当左端点被修改但是右端点没有被修改时

        左端点花费必须修改，此时答案也应该被修改

        右端点同理

        当左端点跟原来左端点相同时 修改左端点花费为较小值

        右端点同理

        特判
        左端点右端点将原来区间全部覆盖时，应该输出答案，


    */

    int t;

    cin>>t;


    while(t--)
    {

        int n;

        cin>>n;


        for(int i=1;i<=n;i++)
        {
            cin>>lef[i]>>righ[i]>>cost[i];
        }

        ll ans=0x7f7f7f7f7f7f7f7f;

        ll leftans=ans,rightans=ans;

        ll l=ans,r=0;


        for(int i=1;i<=n;i++)
        {

            if(l>lef[i])
            {
                l=lef[i];

                leftans=cost[i];

                ans=leftans+rightans;


            }
            else if(l==lef[i])
            {

                leftans=min(leftans,cost[i]);

                ans=min(ans,leftans+rightans);



            }

            if(r<righ[i])
            {
                r=righ[i];

                rightans=cost[i];


                ans=leftans+rightans;

            }
            else if(r==righ[i])
            {
               rightans=min(rightans,cost[i]);


               ans=min(ans,leftans+rightans);


            }

            if(r==righ[i]&&l==lef[i])
            {
                ans=min(ans,cost[i]);

            }


            cout<<ans<<endl;


        }

    }

    return 0;

}