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 <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <bitset>#include <map>#include <queue>#include <stack>#include <vector>#include <cassert>#define rep(i,m,n) for(i=m;i<=n;i++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define sys system("pause")const int maxn=1e6+10;const int N=2e5+10;using namespace std;int id(int l,int r){return l+r|l!=r;}ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}int n,m,k,t,mi[maxn<<1],tag[maxn<<1],q,ql[maxn],qr[maxn],qt[maxn],ip[maxn],cnt;double a[maxn];bool cmp(int x,int y){return qt[x]>qt[y];}void pdw(int x,int y,int rt){    int mid=x+y>>1,ls=id(x,mid),rs=id(mid+1,y);    mi[ls]=mi[rs]=tag[rt];    tag[ls]=tag[rs]=tag[rt];    tag[rt]=0;}void pup(int x,int y,int rt){    int mid=x+y>>1;    mi[rt]=min(mi[id(x,mid)],mi[id(mid+1,y)]);}void init(int l,int r,int rt){    mi[rt]=0;    tag[rt]=0;    if(l==r)return;    int mid=l+r>>1;    init(l,mid,id(l,mid));    init(mid+1,r,id(mid+1,r));}void upd(int x,int y,int z,int l,int r,int rt){    if(x==l&&y==r)    {        mi[rt]=z;        tag[rt]=z;        return;    }    int mid=l+r>>1;    if(tag[rt])pdw(l,r,rt);    if(y<=mid)upd(x,y,z,l,mid,id(l,mid));    else if(x>mid)upd(x,y,z,mid+1,r,id(mid+1,r));    else upd(x,mid,z,l,mid,id(l,mid)),upd(mid+1,y,z,mid+1,r,id(mid+1,r));    pup(l,r,rt);}int gao(int x,int y,int l,int r,int rt){    if(x==l&&y==r)return mi[rt];    int mid=l+r>>1;    if(tag[rt])pdw(l,r,rt);    if(y<=mid)return gao(x,y,l,mid,id(l,mid));    else if(x>mid)return gao(x,y,mid+1,r,id(mid+1,r));    else return min(gao(x,mid,l,mid,id(l,mid)),gao(mid+1,y,mid+1,r,id(mid+1,r)));}bool ok(int x){    int i,j;    init(1,cnt,id(1,cnt));    rep(i,1,x)ip[i]=i;    sort(ip+1,ip+x+1,cmp);    for(i=1;i<=x;)    {        int l=ql[ip[i]],r=qr[ip[i]],xl=l,xr=r;        j=i;        while(j+1<=x&&qt[ip[j+1]]==qt[ip[i]])l=max(l,ql[ip[j+1]]),r=min(r,qr[ip[j+1]]),xl=min(xl,ql[ip[j+1]]),xr=max(xr,qr[ip[j+1]]),j++;        if(l>r)return false;        if(gao(l,r,1,cnt,id(1,cnt))>qt[ip[i]])return false;        upd(xl,xr,qt[ip[i]],1,cnt,id(1,cnt));        i=j+1;    }    return true;}int main(){    int i,j;    scanf("%d%d",&n,&q);    rep(i,1,q)    {        scanf("%d%d%d",&ql[i],&qr[i],&qt[i]);        if(ql[i]>qr[i])swap(ql[i],qr[i]);        a[++cnt]=ql[i],a[++cnt]=qr[i];    }    sort(a+1,a+cnt+1);    for(i=cnt;i>=1;i--)if(a[i]>a[i-1]+1)a[++cnt]=a[i-1]+1;    sort(a+1,a+cnt+1);    cnt=unique(a+1,a+cnt+1)-a-1;    rep(i,1,q)    {        ql[i]=lower_bound(a+1,a+cnt+1,ql[i])-a;        qr[i]=lower_bound(a+1,a+cnt+1,qr[i])-a;    }    int l=1,r=q,ret;    while(l<=r)    {        int mid=l+r>>1;        if(ok(mid))ret=mid,l=mid+1;        else r=mid-1;    }    assert(ret>=1&&ret<=q);    printf("%d\n",ret+1<=q?ret+1:0);    return 0;}