#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 1e9 + 7;
struct range {
int l;
int r;
range(int xx = 0, int yy = 0) : l(xx), r(yy) {};
};
int nn, kk;
int tree[8000025];
range lazy[8000025];
bool mark[8000025];
void push(int v) {
if (mark[v]) {
if (lazy[v].r < lazy[2 * v].l) {
lazy[2 * v].l = lazy[v].l;
lazy[2 * v].r = lazy[v].r;
}
else if (lazy[v].l > lazy[2 * v].r) {
lazy[2 * v].l = lazy[v].l;
lazy[2 * v].r = lazy[v].r;
}
else {
lazy[2 * v].l = max(lazy[2 * v].l, lazy[v].l);
lazy[2 * v].r = min(lazy[2 * v].r, lazy[v].r);
}
if (lazy[v].r < lazy[2 * v+1].l) {
lazy[2 * v+1].l = lazy[v].l;
lazy[2 * v+1].r = lazy[v].r;
}
else if (lazy[v].l > lazy[2 * v+1].r) {
lazy[2 * v+1].l = lazy[v].l;
lazy[2 * v+1].r = lazy[v].r;
}
else {
lazy[2 * v+1].l = max(lazy[2 * v+1].l, lazy[v].l);
lazy[2 * v+1].r = min(lazy[2 * v+1].r, lazy[v].r);
}
mark[v] = false;
}
}
void update(int v, int tl, int tr, int ll, int rr, int op, int x) {
if (ll > rr) return;
if (ll == tl && rr == tr) {
if (op == 0) {
lazy[v].l = max(lazy[v].l, x);
lazy[v].r = max(lazy[v].r, lazy[v].l);
}
if (op == 1) {
lazy[v].r = min(lazy[v].r, x);
lazy[v].l = min(lazy[v].l, lazy[v].r);
}
mark[v] = true;
return;
}
push(v);
int pos = (tl + tr) / 2;
update(2 * v, tl, pos, ll, min(pos, rr), op, x);
update(2 * v + 1, pos + 1, tr, max(pos + 1, ll), rr, op, x);
}
int get(int v, int tl, int tr, int x) {
if (tl == tr) {
if (tree[x] < lazy[v].l) return lazy[v].l;
if (tree[x] > lazy[v].r) return lazy[v].r;
return tree[x];
}
push(v);
int tm = (tl + tr) / 2;
if (x <= tm) return get(2 * v, tl, tm, x);
else return get(2 * v + 1, tm + 1, tr, x);
}
void update(int ll, int rr, int op, int x) { update(1, 0, 2 * nn + 2, ll, rr, op, x); }
int get(int x) { return get(1, 0, 2 * nn + 2, x); }
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]) {
for (int i = 0; i < n; ++i) tree[i] = 0;
for (int i = 0; i < n; ++i) {
lazy[i].l = 0;
lazy[i].r = 100005;
}
for (int i = 0; i < k; ++i) update(left[i], right[i], op[i] - 1, height[i]);
for (int i = 0; i < n; ++i) finalHeight[i] = get(i);
return;
}
//int main(int argc, char* argv[]) {
// /*const char* FIN = "sample.in";
// const char* FOUT = "sample.out";
// const char* inFile = argc > 1 ? argv[1] : FIN;
// ifstream cin(inFile);
// ofstream cout(FOUT);*/
//
// //cin >> n >> k;
// //for (int i = 0; i < n; ++i) cin >> tree[i];
// //for (int i = 0; i < 8000005; ++i) {
// // lazy[i].l = 0;
// // lazy[i].r = 100005;
// //}
// //for (int i = 0; i < k; ++i) {
// // int o, ll, rr, x;
// // cin >> o >> ll >> rr >> x;
// // update(ll, rr, o, x);
// // //o == 0 means adding, o == 1 means removing
// //}
// //for (int i = 0; i < n; ++i) cout << get(i) << endl;
//
//
// return 0;
//}
