// Skyqwq
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef long long LL;
typedef pair<int, int> PII;


template <typename T> bool inline chkMin(T &x, T y) { return y < x ? x = y, 1 : 0; }
template <typename T> bool inline chkMax(T &x, T y) { return y > x ? x = y, 1 : 0; }

#include "wall.h"

const int N = 2e6 + 5, INF = 1e9;

struct Node{
  int l, r;
} I;

Node operator + (const Node &a, const Node &b) {
  Node c;
  if (b.l >= a.r) c = (Node) { b.l, b.l };
  else if (b.r <= a.l) c = (Node) { b.r, b.r };
  else c = (Node) { max(b.l, a.l), min(a.r, b.r) };
  return c;
}

struct E{
  int op, x, k, o;
};



vector<E> e[N];

Node t[N << 2];

#define ls (p << 1)
#define rs (p << 1 | 1)

void inline pu(int p) {
  t[p] = t[ls] + t[rs];
}

void bd(int p, int l, int r) {
  t[p] = I;
  if (l == r) return;
  int mid = (l + r) >> 1;
  bd(ls, l, mid);
  bd(rs, mid + 1, r);
}

void chg(int p, int l, int r, int x, Node y) {
  if (l == r) {
    t[p] = y; return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) chg(ls, l, mid, x, y);
  else chg(rs, mid + 1, r, x, y);
  pu(p);
}

void buildWall(int n, int k, int op[], int L[], int R[], int H[], int ans[]){
  for (int i = 0; i < k; i++) {
    e[L[i]].pb((E){ op[i], i, H[i], 1});
    e[R[i] + 1].pb((E){ op[i], i, H[i], -1});
  }
  I = (Node) { -INF, INF };
  bd(1, 0, k - 1);
  for (int i = 0; i < n; i++) {
    for (E v: e[i]) {
        if (v.o == -1) chg(1, 0, k - 1, v.x, I);
        else chg(1, 0, k - 1, v.x, v.op == 1 ? (Node) { v.k, INF } : (Node) { -INF, v.k } );
    }
    Node u = t[1];
    if (0 <= u.l) ans[i] = u.l;
    else if (0 >= u.r) ans[i] = u.r;
    else ans[i] = 0;
  }
  return;
}