The cows, who always have an inferiority complex about their intelligence, have a new guessing game to sharpen their brains.

A designated 'Hay Cow' hides behind the barn and creates N (1 ≤ N ≤ 1,000,000) uniquely-sized stacks (conveniently numbered 1..N) of hay bales, each with 1..1,000,000,000 bales of hay.

The other cows then ask the Hay Cow a series of Q (1 ≤ Q ≤ 25,000) questions about the the stacks, all having the same form:

What is the smallest number of bales of any stack in the range of stack numbers Q_l..Q_h (1 ≤ Q_l ≤ N; Q_l ≤ Q_h ≤ N)?

The Hay Cow answers each of these queries with a single integer A whose truthfulness is not guaranteed.

Help the other cows determine if the answers given by the Hay Cow are self-consistent or if certain answers contradict others.

* Line 1: Two space-separated integers: N and Q
* Lines 2..Q+1: Each line contains three space-separated integers that represent a single query and its reply: Q_l, Q_h, and A

* Line 1: Print the single integer 0 if there are no inconsistencies among the replies (i.e., if there exists a valid realization of the hay stacks that agrees with all Q queries). Otherwise, print the index from 1..Q of the earliest query whose answer is inconsistent with the answers to the queries before it.

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <queue>

 #include <set>

 const int INF=0x3f3f3f3f;

 using namespace std;

 #define maxn 1000010

 struct node{

     int l;

     int r;

     int num;

 };

 int n,q;

 int fa[maxn];

 node a[maxn];

 node tmp[maxn];

 int Find(int x)

 {

     return x==fa[x]?x:fa[x]=Find(fa[x]);

 }

 bool cmp(node a,node b)

 {

     return a.num>b.num;

 }

 bool judge(int tot)

 {

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

         fa[i]=i;

     for(int i=;i<=tot;i++)

         tmp[i]=a[i];

     sort(tmp+,tmp++tot,cmp);

     for(int i=,j;i<=tot;i=j+)

     {

         j=i;

         int l=tmp[i].l;

         int r=tmp[i].r;

         int L=tmp[i].l;

         int R=tmp[i].r;

         while(j<tot&&tmp[j].num==tmp[j+].num)

         {

             j++;

             l=max(l,tmp[j].l);//取交集

             r=min(r,tmp[j].r);

             L=min(L,tmp[j].l);//取并集

             R=max(R,tmp[j].r);

         }

         if(l>r||l>Find(r))//为空或无未染色点

             return ;

         while(L<=R)

         {

             if(Find(R)==R)

             {

                 fa[R]=Find(L-);//染色

                 R--;

             }

             else

                 R=fa[R];//直接跳转到其父节点

         }

     }

     return ;

 }

 int main()

 {

     scanf("%d %d",&n,&q);

     for(int i=;i<=q;i++)

     {

         scanf("%d %d %d",&a[i].l,&a[i].r,&a[i].num);

     }

     int L=;

     int R=q;

     int ans=;

     while(L<=R)

     {

         int mid=(L+R)/;

         if(judge(mid))

             L=mid+;

         else

         {

             ans=mid;

             R=mid-;

         }

     }

     printf("%d\n",ans);

     return ;

 }