#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
struct LazySegmentTree{
int siz;
vector<ll>tree,lazyAdd,lazySub;
LazySegmentTree(int temp){
siz=temp;
while ((siz&(siz-1))!=0) siz++;
for (int i=0;i<siz*2;i++){
tree.push_back(0);
lazyAdd.push_back(-INF);
lazySub.push_back(INF);
}
}
void calc(int node){
tree[node]=max(tree[node],lazyAdd[node]);
tree[node]=min(tree[node],lazySub[node]);
}
void propagate(int node, int L, int R){
calc(node);
if (L!=R){
calc(node*2);
calc(node*2+1);
applySub(node*2,lazySub[node]);
applyAdd(node*2,lazyAdd[node]);
applySub(node*2+1,lazySub[node]);
applyAdd(node*2+1,lazyAdd[node]);
calc(node*2);
calc(node*2+1);
}
lazyAdd[node]=-INF;
lazySub[node]=INF;
}
void applyAdd(int node, ll x){
if (x>lazyAdd[node]){
lazyAdd[node]=x;
lazySub[node]=max(lazySub[node],x);
}
}
void applySub(int node, ll x){
if (x<lazySub[node]){
lazySub[node]=x;
lazyAdd[node]=min(lazyAdd[node],x);
}
}
void update(int node, int L, int R, int i, int j, ll x, int type){
propagate(node,L,R);
if (L>R || L>j || R<i)
return;
if (L>=i && R<=j){
if (type==1)
applyAdd(node,x);
else
applySub(node,x);
propagate(node,L,R);
return;
}
update(node*2,L,(L+R)/2,i,j,x,type);
update(node*2+1,(L+R)/2+1,R,i,j,x,type);
//tree[node]=tree[node*2]+tree[node*2+1];
}
ll query(int node, int L, int R, int i,int j){
if (L>R || L>j || R<i)
return 0;
propagate(node,L,R);
//cout<<"QPOP "<<node<<endl;
if (L>=i && R<=j){
//cout<<"FOUND "<<node<<endl;
return tree[node];
}
ll q1=query(node*2,L,(L+R)/2,i,j);
ll q2=query(node*2+1,(L+R)/2+1,R,i,j);
return q1+q2;
}
ll query(int i, int j){ return query(1,0,siz-1,i,j); }
void update(int i, int j, ll val, int type){ update(1,0,siz-1,i,j,val,type); }
};
void buildWall(int N, int K, int op[], int l[], int r[], int h[], int finalh[]){
LazySegmentTree lst=LazySegmentTree(N);
for (int i=0;i<K;i++){
lst.update(l[i],r[i],h[i],op[i]);
/*
bool debug=false;
if (debug){
cout<<"BEFORE: "<<endl;
for (int j=1;j<lst.siz*2;j++)
cout<<j<<": "<<lst.lazyAdd[j]<<' '<<lst.lazySub[j]<<endl;
}
for (int j=0;j<N;j++)
cout<<lst.query(j,j)<<' ';
cout<<endl;
if (debug){
cout<<"AFTER: "<<endl;
for (int j=1;j<lst.siz*2;j++)
cout<<j<<": "<<lst.lazyAdd[j]<<' '<<lst.lazySub[j]<<endl;
}
*/
}
for (int i=0;i<N;i++)
finalh[i]=lst.query(i,i);
}
