#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>
const int max_n=2000000;
int nodes[max_n<<2][2];
int L[max_n<<2], H[max_n<<2];
template<class U, class V> void maximize(U& a, V b) { if (a<b) a=b; }
template<class U, class V> void minimize(U& a, V b) { if (a>b) a=b; }
const int inf=1e9+9;
void buildRange(int node, int low, int high) {
L[node]=low, H[node]=high;
if (low==high) {
nodes[node][0]=0, nodes[node][1]=inf;
return ;
}
int mid=low+high>>1;
buildRange(node<<1, low, mid);
buildRange(node<<1|1, mid+1, high);
}
void lazyPush(int node) {
for (int j=2*node; j<2*node+2; ++j) {
maximize(nodes[j][0], nodes[node][0]);
maximize(nodes[j][1], nodes[j][0]);
minimize(nodes[j][1], nodes[node][1]);
minimize(nodes[j][0], nodes[j][1]);
}
nodes[node][0]=0;
nodes[node][1]=inf;
}
void update(int node, int leftq, int rightq, int op, int height) {
if (leftq<=L[node] and rightq>=H[node]) {
if (op==1) {
maximize(nodes[node][0], height);
maximize(nodes[node][1], height);
}
else {
minimize(nodes[node][0], height);
minimize(nodes[node][1], height);
}
return ;
}
lazyPush(node);
if (H[node<<1]>=leftq) update(node<<1, leftq, rightq, op, height);
if (L[node<<1|1]<=rightq) update(node<<1|1, leftq, rightq, op, height);
}
void modify(int node, int finalHeight[]) {
if (L[node]==H[node]) {
finalHeight[H[node]-1]=nodes[node][0];
return ;
}
lazyPush(node);
modify(node<<1, finalHeight);
modify(node<<1|1, finalHeight);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
buildRange(1, 1, n);
for (int i=0; i<k; ++i) {
update(1, 1+left[i], 1+right[i], op[i], height[i]);
}
modify(1, finalHeight);
}
/*
int main() {
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
int n, k; std::cin>>n>>k;
int op[k], left[k], right[k], height[k];
for (int i=0; i<k; ++i) {
std::cin>>op[i]>>left[i]>>right[i]>>height[i];
}
int finalHeight[n];
buildWall(n, k, op, left, right, height, finalHeight);
for (int i=0; i<n; ++i) {
std::cout<<finalHeight[i]<<" ";
}
std::cout<<std::endl;
return 0;
}
*/
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
