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

using namespace std;

namespace {

const int N = 2e6 + 7;
const int INF = 1e9;

int d[4 * N], d1[4 * N];
int t[4 * N];

// v = max(min(max(min(v, d), d1), x), x1)


// v = max(min(v, d), d1)

// v = max(min(v, x), x1)

void apply(int v, int x, int x1) {
	t[v] = min(t[v], x);
	t[v] = max(t[v], x1);
	d1[v] = min(d1[v], x);
	d[v] = min(d[v], x);
	d1[v] = max(d1[v], x1);
}

void push(int v) {
	apply(2 * v, d[v], d1[v]);
	apply(2 * v + 1, d[v], d1[v]);
	d[v] = INF;
	d1[v] = -INF;	
}

void upd(int v, int tl, int tr, int l, int r, int x, int x1) {
	if (tl >= r || tr <= l) return;
	if (tl >= l && tr <= r) {
		apply(v, x, x1);
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(2 * v, tl, tm, l, r, x, x1);
	upd(2 * v + 1, tm, tr, l, r, x, x1);
	t[v] = t[2 * v];
}

void findheights(int v, int tl, int tr, int finalHeight[]) {
	if (tr - tl == 1) {
		finalHeight[tl] = t[v];
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	findheights(2 * v, tl, tm, finalHeight);
	findheights(2 * v + 1, tm, tr, finalHeight);
}

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < 4 * n; ++i) {
		t[i] = 0;
		d[i] = INF;
		d1[i] = -INF;
	}
	for (int i = 0; i < k; ++i) {
		if (op[i] == 1) {
			upd(1, 0, n, left[i], right[i] + 1, INF, height[i]);
		} else {
			upd(1, 0, n, left[i], right[i] + 1, height[i], -INF);
		}
	}
	findheights(1, 0, n, finalHeight);
}