#include <bits/stdc++.h>
#include "wall.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas + son)/2)
#define sol (k+k)
#define sag (k+k+1)
#define inf 1000000007
#define N 2000005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
int n;
ii seg[4*N];
void put(int k, int bas, int son, int op, int z){
// cout << op << endl;
// cout << "BAK" << bas << " " << son << " " << seg[k].st << " " << seg[k].nd << endl;
if(op == 1){
if(z >= seg[k].nd)
seg[k] = mp(z, z);
if(z >= seg[k].st)
seg[k].st = z;
}
if(op == 0){
if(z <= seg[k].st)
seg[k] = mp(z, z);
if(z <= seg[k].nd){
seg[k].nd = z;
// cout << z << " yaptim amk" << endl;
}
}
// cout << "AMK" << bas << " " << son << " " << seg[k].st << " " << seg[k].nd << endl;
}
void push(int k, int bas, int son){
if(seg[k].st != 0){
put(sol, bas, orta, 1, seg[k].st);
put(sag, orta + 1, son, 1, seg[k].st);
}
if(seg[k].nd != inf){
put(sol, bas, orta, 0, seg[k].nd);
put(sag, orta + 1, son, 0, seg[k].nd);
}
seg[k] = mp(0, inf);
}
void up(int k, int bas, int son, int x, int y, int op, int z){
if(bas > y or son < x)
return;
if(bas >= x and son <= y){
put(k, bas, son, op, z);
return;
}
push(k, bas, son);
up(sol, bas, orta, x, y, op, z);
up(sag, orta + 1, son, x, y, op, z);
// seg[k].st = min(seg[sol].st, seg[sag].st);
// seg[k].nd = max(seg[sol].nd, seg[sag].nd);
}
int qu(int k, int bas, int son, int x){
if(bas == son){
// if(seg[k].st != seg[k].nd){
// cout << "OF MAK " << seg[k].st << " " << seg[k].nd << endl;
// }
return seg[k].st;
}
push(k, bas, son);
if(x <= orta)
return qu(sol, bas, orta, x);
else
return qu(sag, orta + 1, son, x);
}
void bu(int k, int bas, int son){
if(bas == son){
seg[k] = mp(0, inf);
return;
}
bu(sol, bas, orta);
bu(sag, orta + 1, son);
seg[k] = mp(0, inf);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
bu(1, 1, n);
for(int i = 0; i < k; i++){
// printf("%d %d %d %d\n", left[i] + 1, right[i] + 1, op[i], height[i] );
up(1, 1, n, left[i] + 1, right[i] + 1, 2 - op[i], height[i]);
}
for(int i = 1; i <= n; i++)
finalHeight[i - 1] = qu(1, 1, n, i);
return;
}
// int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// int n;
// int k;
// int i, j;
// int status = 0;
// status = scanf("%d%d", &n, &k);
// assert(status == 2);
// int* op = (int*)calloc(sizeof(int), k);
// int* left = (int*)calloc(sizeof(int), k);
// int* right = (int*)calloc(sizeof(int), k);
// int* height = (int*)calloc(sizeof(int), k);
// int* finalHeight = (int*)calloc(sizeof(int), n);
// for (i = 0; i < k; i++){
// status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
// assert(status == 4);
// }
// buildWall(n, k, op, left, right, height, finalHeight);
// for (j = 0; j < n; j++)
// printf("%d\n", finalHeight[j]);
// return 0;
// }
