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

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

struct node;

node *newnode();
 
struct node
{
	node *c[2];

	int label_Min, label_Max;
 
	node(): label_Min(oo), label_Max(-oo) { memset(c, 0, sizeof c); }

	void flag_label(int _Min, int _Max)
	{
		chkmin(label_Min, _Min);
		chkmax(label_Min, _Max);
		chkmin(label_Max, _Min);
		chkmax(label_Max, _Max);
	}

	void push_down()
	{
		if (label_Min != oo || label_Max != -oo)
		{
			REP(i, 0, 2) 
			{
				if (!c[i]) c[i] = newnode();
				c[i]->flag_label(label_Min, label_Max);
			}
			label_Min = oo, label_Max = -oo;
		}
	}
 
};

const int max0 = 100000;
 
node *nd_pool;
int nd_res = 0;
 
node *newnode()
{
	if (!nd_res) nd_pool = new node[max0], nd_res = max0;
	return nd_pool + (--nd_res);
}
 
node *rt;
 
int seg_x, seg_y, seg_Min, seg_Max;
int *seg_ret;
 
void add(node *&rt, int l, int r)
{
	if (!rt) rt = newnode();
	if (seg_x <= l && r <= seg_y)
	{
		rt->flag_label(seg_Min, seg_Max);
		return;
	}
	int mid = (l + r) >> 1;
	rt->push_down();
	if (seg_x < mid) add(rt->c[0], l, mid);
	if (seg_y > mid) add(rt->c[1], mid, r);
}

int n;

inline void seg_add(int x, int y, int Min, int Max)
{
	seg_x = x, seg_y = y, seg_Min = Min, seg_Max = Max;
	add(rt, 0, n);
}

void print(node *rt, int l, int r)
{
	if (!rt) return;
	if (r - l <= 1)
	{
		chkmin(seg_ret[l], rt->label_Min);
		chkmax(seg_ret[l], rt->label_Max);
		return;
	}
	int mid = (l + r) >> 1;
	rt->push_down();
	print(rt->c[0], l, mid);
	print(rt->c[1], mid, r);
}

void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	n = _n;
	REP(i, 0, k)
	{
		if (op[i] == 1) seg_add(left[i], right[i] + 1, oo, height[i]);
		else seg_add(left[i], right[i] + 1, height[i], -oo);
	}
	seg_ret = finalHeight;
	REP(i, 0, n) seg_ret[i] = 0;
	print(rt, 0, n);
}