*C. Knight Tournament

C. Knight Tournament

Hooray! Berl II, the king of Berland is making a knight tournament. The king has already sent the message to all knights in the kingdom and they in turn agreed to participate in this grand event.

As for you, you're just a simple peasant. There's no surprise that you slept in this morning and were late for the tournament (it was a weekend, after all). Now you are really curious about the results of the tournament. This time the tournament in Berland went as follows:

• There are n knights participating in the tournament. Each knight was assigned his unique number — an integer from 1 to n.
• The tournament consisted of m fights, in the i-th fight the knights that were still in the game with numbers at least li and at most rihave fought for the right to continue taking part in the tournament.
• After the i-th fight among all participants of the fight only one knight won — the knight number xi, he continued participating in the tournament. Other knights left the tournament.
• The winner of the last (the m-th) fight (the knight number xm) became the winner of the tournament.

You fished out all the information about the fights from your friends. Now for each knight you want to know the name of the knight he was conquered by. We think that the knight number b was conquered by the knight number a, if there was a fight with both of these knights present and the winner was the knight number a.

Write the code that calculates for each knight, the name of the knight that beat him.

Input

The first line contains two integers n, m (2 ≤ n ≤ 3·105; 1 ≤ m ≤ 3·105) — the number of knights and the number of fights. Each of the following m lines contains three integers li, ri, xi (1 ≤ li < ri ≤ n; li ≤ xi ≤ ri) — the description of the i-th fight.

It is guaranteed that the input is correct and matches the problem statement. It is guaranteed that at least two knights took part in each battle.

Output

Print n integers. If the i-th knight lost, then the i-th number should equal the number of the knight that beat the knight number i. If the i-th knight is the winner, then the i-th number must equal 0.

Examples

input

4 3
1 2 1
1 3 3
1 4 4

output

3 1 4 0 

input

8 4
3 5 4
3 7 6
2 8 8
1 8 1

output

0 8 4 6 4 8 6 1 

Note

Consider the first test case. Knights 1 and 2 fought the first fight and knight 1 won. Knights 1 and 3 fought the second fight and knight 3 won. The last fight was between knights 3 and 4, knight 4 won.

=========================editorial===============================================

Let's the current fight (l, r, x) consists of K knights fighting. Then all we have to do is to find all these knights in time O(K) orO(KlogN). There are several ways to do that, let's consider some of them.

The first way is to store the numbers of all alive knights in std::set (C++) or TreeSet (Java). Then in C++ we can use lower_bound method to find the first knight in the fight that is alive, and to iterate over this set, each time moving to the next alive knight. In Java we should use subSet method.

    set<int> alive;
    for (int i = 0; i < n; i++)
        alive.insert(i);
        
    for (int i = 0; i < m; i++) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        l--, r--, x--;        
        set<int>::iterator it = alive.lower_bound(l);
        vector<int> toErase;        
        while(it != alive.end()){
            int cur = *it;            
            if(cur > r)
                break;                
            if(cur != x){    
                toErase.pb(cur); answer[cur] = x;
            }
            it++;
        }

        for (size_t j = 0; j < toErase.size(); j++)
            alive.erase(toErase[j]);
    }

The second way is to define array next with the following meaning:

• if knight v is alive, then next[v] = v;
• if knight v is out of tournament, next[v] points to some knight u (next[v] = u), such that there are no alive knights between v and u;

To find the first alive knight starting from the knight v we need to follow this links until we find the first knight w with next[w] = w. In order not to pass the same links too many times, we will use the trick known as path compression (it is used in Disjoint Set Union). Note that you should handle the case when the current knight is the last knight and is out of tournament.

    int getNext(int v){
        if(next[v] == v)
            return v;
        return next[v] = getNext(next[v]);
    }

    ...

     int cur = getNext(l);
     while(cur <= r){
        if(cur == x){
            cur = cur + 1;
        }else{
            answer[cur] = x;
            next[cur] = cur + 1;
        }

        cur = getNext(cur);
    }

==========================================code===========================================

#include<bits/stdc++.h>
using namespace std;
int nextt[1000000];
int ans[1000000];
set<int> s;
int main()
{
  int n,m;
   cin>>n>>m;
   for(int i=1;i<=n+3;i++)
    {
      nextt[i]=i+1;
      s.insert(i);
    }
    for(int i=0;i<m;i++)
    {
      int l,r,w;
      scanf("%d %d %d",&l,&r,&w);
     set<int>:: iterator it;
     it=lower_bound(s.begin(),s.end(),l-1);
      int  a=0,b=0,c=0,d=0;
     if(*it<l)
         {
        a=*it;
        b=w;
   }
   it=lower_bound(s.begin(),s.end(),r+1);
   if(it!=s.end())
    {
    
     c=w;
     d=*it;
    }
     int cur=*lower_bound(s.begin(),s.end(),l);
     
    while(cur<=r)
     {
       if(ans[cur]==0  && cur!=w)
          {
           ans[cur]=w;
           s.erase(cur); 
     }
     cur=nextt[cur];
     }
     nextt[a]=b;
     nextt[c]=d;
    }
    for(int i=1;i<=n;i++)
     printf("%d ",ans[i]);
}

***Maximum K Sums ( find all possible sub array sum and print firs k maximum sum )

Maximum K Sums

Chef likes arrays a lot. Today, he found an array A consisting of N positive integers.

Let L denote the sorted (in non-increasing order) list of size N*(N+1)/2 containing the sums of all possible contiguous subarrays of A. Chef is interested in finding the first K elements from the list L. Can you help him in accomplishing this task?

Input

There is only a single test case per input file.

The first line of input contains two space separated integer numbers N and K denoting the size of the array and the number of the maximal sums you need to find.

The following line contains N space separated integer numbers denoting the array A.

Output

Output K space separated integers where the i^th integer denotes the i^th element of L.

Constraints

• 1 ≤ N ≤ 10⁵


• 1 ≤ K ≤ min(N*(N+1)/2, 10⁵)


• 1 ≤ A_i ≤ 10⁹

Subtasks

• Subtask 1 (47 pts) : 1 ≤ N ≤ 1000, 1 ≤ K ≤ min{N*(N+1)/2, 10⁵}
• Subtask 2 (53 pts) : 1 ≤ N ≤ 10⁵, 1 ≤ K ≤ min{N*(N+1)/2, 10⁵}

Example

Input 1
3 4
1 3 4

Output 1
8 7 4 4

Input 2
3 3
10 2 7

Output 2
19 12 10

Explanation

Test 1:

--------------------------------------EDITORIAL-----------------------------------------------------------

PREREQUISITES:

Sorting, Greedy, Data Structure, Implementation.

PROBLEM STATEMENT:

Given an array A$A$ containing N$N$ positive integers and an integer K$K$. We are asked to report the largest K$K$ values from the list of sums of all possible subarrays of array A$A$.

EXPLANATION:

Subtask 1

Listing sums of all the possible subarrays of A$A$ and finding the largest K$K$ values will be enough to pass this subtask.

C++ Code

#define ll long long
void solve(int N, int K, int *arr) {
    vector<ll> sum;
    for(int i=1;i<=n;i++) {
        long long int s = 0;
        for(int j=i;j<=n;j++) {
            s += arr[j];
            sum.push_back(s);
        }
    }
    sort(sum.rbegin(), sum.rend());
    for(int i=0; i<=K-1; i++) cout << sum[i] << " ";
    cout << "\n";
}

Time Complexity

O((N×(N+1)2))×logN×(N+1)2)$O((\frac{N\times (N+1)}{2}))\times \log \frac{N\times (N+1)}{2})$

Complete Code Link

Note

Although the above solution will get passed on first subtask but we can have slight better complexity by maintaining a priority queue for the first K$K$ elements instead of sorting all the sums.

Complete Code Link

Subtask 2

It is easy to see that the above solution will time out for this subtask.

Then, how to approach it ?

It can be noticed that the largest and first value will always be sum of all the elements as it is given that all elements are positive integers. It means the sum is corresponding to the subarray [1toN]$[1toN]$ inclusively. Now, we have taken up the range 1...N$\mathrm{1...}N$ and we can see that the next possible largest sum will be the maximum of sum of range 2...N$\mathrm{2...}N$ and range 1...N−1$\mathrm{1...}N-1$. Let us assume that the second largest is obtained from the range 1...N−1$\mathrm{1...}N-1$. Then, the third largest sum will be maximum of sum of range 2...N$\mathrm{2...}N$ ( previous range left ), range 2...N−1$\mathrm{2...}N-1$ and range 1...N−2$\mathrm{1...}N-2$ ( new ranges ). The above procedure can be run K$K$ times to find the largest K$K$ values.

How to implement above idea ?

Let us maintain a priority queue S$S$ ( set can also be used in C++ ). So, whenever we are taking the sum of a range say [L to R] from S, we can simply insert 2 new values to S$S$ i.e sum of range [L+1toR]$[L+1toR]$ and [LtoR−1]$[LtoR-1]$ if L!=R$L!=R$. Note that along with sum of range we are also maintaining the indices i.e L$L$ and R$R$ denoting that range in our priority queue.

C++ Code

#define ll long long
void solve(int N, int K, int *arr) {
    set<pair<ll,pair<int,int>> S;
    long long int prefix_sum[N+1];
    for(int i=1;i<=n;i++) {
        prefix_sum[i] = prefix_sum[i-1] + arr[i];
    }

    S.insert({prefix_sum[N], {1, N}});
    while( K -- && !S.empty() ) {
        pair<ll,pair<int,int>> top = *S.begin();
        S.erase( top );
        long long int sum;
        int L, R;
        sum = top.first;
        L = top.second.first;
        R = top.second.second;
        cout << sum <<" ";
        if( L != R ) {
            S.insert({sum-arr[L], {L+1, R}});
            S.insert({sum-arr[R], {L, R-1}});
        }
    }   
} 

TIME COMPLEXITY:

O(K×logK)$O(K\times \log K)$

-------------------------------CODE--------------------------------------------------------

// I USED SET INSTEAD OF PQ

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

set<pair<pair<lli,int>,int> > s;

map<pair<int,int> ,int> ma;

lli arr[1000000];

int main()

 {

  int n,m;

  cin>>n>>m;

  lli sum=0;

  for(int i=0;i<n;i++)

   {

    cin>>arr[i];

    sum+=arr[i];

  }

  s.insert({{sum,0},n-1});

for(int i=0;i<m;i++)

{

 while(1)

  {

  set<pair<pair<lli,int>,int> > :: reverse_iterator ite;

  ite=s.rbegin();

  pair<pair<lli,int>,int> pp;

  lli sum=ite->first.first;

  int l=ite->first.second;

  int  r=ite->second;

   s.erase({{sum,l},r});

 

   if(ma[{l,r}]==0)

    {

    ma[{l,r}]=1;

    cout<<sum<<" ";

    s.insert({{sum-arr[l],l+1},r});

    s.insert({{sum-arr[r],l},r-1});

    break;

 }

   

 

}

}

   

 }