#include <bits/stdc++.h>
#include "wall.h"

using namespace std;
typedef long long ll;
const int maxn = 2000012;

int mx[maxn*4], mn[maxn*4];
int p[maxn*4];

void push(int v, int tl, int tr){
    if(tl == tr || p[v] == -1) return;
    mx[v*2] = mx[v*2+1] = p[v];
    mn[v*2] = mn[v*2+1] = p[v];
    p[v*2] = p[v*2+1] = p[v];
    p[v] = -1;
}

void upd(int v, int tl, int tr, int l, int r, int x, int tp){
    push(v, tl, tr);
    if(tl > r || l > tr || tp == 1 && mn[v] >= x || tp == 2 && mx[v] <= x) return;
    if(tl >= l && tr <= r && (tp == 1 && mx[v] <= x || tp == 2 && mn[v] >= x)){
        mx[v] = mn[v] = x;
        p[v] = x;
        return;
    }
    int mid = tl + tr >> 1;
    upd(v*2, tl, mid, l, r, x, tp);
    upd(v*2+1, mid+1, tr, l, r, x, tp);
    mx[v] = max(mx[v*2], mx[v*2+1]);
    mn[v] = min(mn[v*2], mn[v*2+1]);
}

int get(int v, int tl, int tr, int pos){
    push(v, tl, tr);
    if(tl == tr){
        return mx[v];
    }
    int mid = tl + tr >> 1;
    if(pos <= mid) return get(v*2, tl, mid, pos);
    return get(v*2+1, mid+1, tr, pos);
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
    for(int i=0;i<n*4;i++){
        p[i] = -1;
    }
    for(int i=0;i<k;i++){
        upd(1, 0, n-1, l[i], r[i], h[i], op[i]);
    }
    for(int i=0;i<n;i++){
        ans[i] = get(1, 0, n-1, i);
    }
}