#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[8000055];
range lazy[8000055];
bool mark[8000055];
void app(int i, int j) {
lazy[i].l = max(lazy[i].l, lazy[j].l);
lazy[i].r = max(lazy[i].r, lazy[j].l);
lazy[i].l = min(lazy[i].l, lazy[j].r);
lazy[i].r = min(lazy[i].r, lazy[j].r);
}
void push(int v) {
app(2 * v, v);
app(2 * v + 1, v);
lazy[v].l = 0;
lazy[v].r = 100005;
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) {
// cout << lazy[v].l << " " << lazy[v].r << "; ";
return lazy[v].l;
}
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, nn+1, ll, rr, op, x); }
int get(int x) { return get(1, 0, nn+1, x); }
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]) {
nn = n;
kk = k;
for (int i = 0; i < n; ++i) tree[i] = 0;
for (int i = 0; i < 8000055; ++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 >> nn >> kk;
// for (int i = 0; i < nn; ++i) cin >> tree[i];
// for (int i = 0; i < 8000005; ++i) {
// lazy[i].l = 0;
// lazy[i].r = 100005;
// }
// for (int i = 0; i < kk; ++i) {
// int o, ll, rr, x;
// cin >> o >> ll >> rr >> x;
// update(ll, rr, o, x);
// for (int i = 0; i < nn; ++i) cout << get(i) << " ";
//
// cout << endl;
// //o == 0 means adding, o == 1 means removing
// }
// for (int i = 0; i < nn; ++i) cout << get(i) << endl;
//
//
// return 0;
//}
