I was solving this question which appeared in triology innovation's OA,Can someone tell me what am i doing wrong in this ?

Question goes like this

Given an array A of n elements representing the monsters and an array B of q elements representing the heros. The i−th type of monster is represented by A[i][0] , A[i][1] and A[i][2] which means a monster of the i−th type is present at each integer co-ordinate from A[i][0] to A[i][1] and having a strength of A[i][2]. The i−th type of hero is represented by B[i][0] and B[i][1] which means a hero of strength B[i][1] will appear at the integer point B[i][0] after i seconds. When the i−th hero appears it will destroy each and every monster present at B[i][0] and having a strength less than B[i][1] . For each i you have to determine the number of monsters left after the i−th hero has completed their task.

Input

The first line of input contains two integers N (1≤N≤105) and Q (1≤Q≤105) — the number of monsters and the number of heroes respectively.The next n lines contains 3 integers A[i][0],A[i][1],A[i][2] (1≤A[i][0]≤A[i][1]≤105;1≤A[i][2]≤109) each describing the monsters. The next q lines contains 2 integers B[i][0],B[i][1] (1≤B[i][0]≤105;1≤B[i][1]≤109) each describing the heroes.

Output

Print q space separated integers — the i−th number should be equal to the number of monsters left after the i−th hero has completed their task.

Examples

Input

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

Output

11 9

Here is My Code: struct seg_tree{ vector st,lazy; int size; seg_tree(int n){ this->size=n; st.resize(4*n); lazy.resize(4*n); } void update(int start,int end){ update(0,0,size-1,start,end); } void update(int node,int l,int r,int start,int end){ if(lazy[node]!=0){ st[node]+=(lazy[node]*(r-l+1)); if(l!=r){ lazy[2*node+1]+=lazy[node]; lazy[2*node+2]+=lazy[node]; } lazy[node]=0; } if(l>end || r<start) return; if(l>=start && r<=end){ st[node]+=(r-l+1); if(l!=r){ lazy[2*node+1]++; lazy[2*node+2]++; } return; } int mid=l+(r-l)/2; update(2*node+1,l,mid,start,end); update(2*node+2,mid+1,r,start,end); st[node]=st[2*node+1]+st[2*node+2]; } int query(int start,int end){ return query(0,0,size-1,start,end); } int query(int node,int l,int r,int start,int end){ if(lazy[node]!=0){ st[node]+=(lazy[node]*(r-l+1)); if(l!=r){ lazy[2*node+1]+=lazy[node]; lazy[2*node+2]+=lazy[node]; } lazy[node]=0; } if(end < l || start > r) return 0; if(l>=start && r<=end){ int val=st[node]; st[node]=0; return val; } int mid=l+(r-l)/2; return query(2*node+1,l,mid,start,end)+query(2*node+2,mid+1,r,start,end); } }; void solve(){ int n,m; cin>>n>>m; vector<vector> monst(n,vector(3)),hero(m,vector(4)); int total=0,mx=0; for(int i=0;i<n;i++){ cin>>monst[i][0]>>monst[i][1]>>monst[i][2]; mx=max({mx,monst[i][0],monst[i][1]}); total+=(monst[i][1]-monst[i][0]+1); }

unordered_map<int,int> high_before;
for(int i=0;i<m;i++){
    cin>>hero[i][0]>>hero[i][1];
    hero[i][2]=i;
    mx=max(mx,hero[i][0]);
    if(high_before[hero[i][0]] >= hero[i][1]){
        hero[i][3]=0;
    }else{
        hero[i][3]=1;
        high_before[hero[i][0]]=hero[i][1];
    }
}
sort(all(monst),[&](vector<int>& a,vector<int>& b){
    return a[2]<b[2]; 
});
sort(all(hero),[&](vector<int>& a,vector<int>& b){
    return a[1]<b[1]; 
});
vector<int> ans(m);
int i=0,j=0;
seg_tree *tree=new seg_tree(mx+1);
while(j<m){
    while(i<n && (monst[i][2]<hero[j][1])){
        int start=monst[i][0],end=monst[i][1];
        tree->update(start,end);
        i++;
    }
    if(hero[j][3]==0){
        j++;
        continue;
    }
    int curr_idx=hero[j][2];
    // cout<<tree->query(hero[j][0]],hero[j][0]])<<endl;
    int monst_at_pos=tree->query(hero[j][0],hero[j][0]);
    ans[curr_idx]=monst_at_pos;
    j++;
}
for(int i:ans){
    total-=i;
    cout<<total<<" ";
}
cout<<endl;

}