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

using namespace std;
const int N = 2e6 + 5; 

int n, m; 
int mx[N * 4], mn[N * 4]; 

inline void ckmax(int o, int k) {
    if (mx[o] < k) mx[o] = k; 
    if (mn[o] < k) mn[o] = k; 
}
inline void ckmin(int o, int k) {
    if (mx[o] > k) mx[o] = k; 
    if (mn[o] > k) mn[o] = k; 
}
inline void pushdown(int o) {
    ckmax(o << 1, mx[o]); ckmax(o << 1 | 1, mx[o]); 
    ckmin(o << 1, mn[o]); ckmin(o << 1 | 1, mn[o]); 
    mx[o] = 0; mn[o] = 1e9; 
}
void update(int o, int l, int r, int x, int y, int k, int type) {
    if (x <= l && r <= y) {
        if (type == 1) ckmax(o, k); 
        else ckmin(o, k); 
        return; 
    }
    pushdown(o); int mid = l + r >> 1; 
    if (x <= mid) update(o << 1, l, mid, x, y, k, type); 
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k, type); 
}
int tot; 
void query(int o, int l, int r, int ans[]) {
    if (l == r) return ans[tot++] = mx[o], void(); 
    pushdown(o); int mid = l + r >> 1; 
    query(o << 1, l, mid, ans); query(o << 1 | 1, mid + 1, r, ans); 
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	::n = n; ::m = k; 
    memset(mn, 0x3f, sizeof mn); 
    for (int i = 0; i < m; ++i) update(1, 1, n, left[i] + 1, right[i] + 1, height[i], op[i]); 
    query(1, 1, n, finalHeight); 
}