#include "wall.h"

#include <bits/stdc++.h>

constexpr int inf = 1.1e9;

struct Cum {
    int l, r;

    Cum(int val = 0) : l(val), r(val) { ; }
    Cum(int l, int r) : l(l), r(r) { ; }
};

int cut_to(int val, int l, int r) {
    return std::max(l, std::min(val, r));
}

Cum merge(Cum a, const Cum& b) {
    a.l = cut_to(a.l, b.l, b.r);
    a.r = cut_to(a.r, b.l, b.r);
    assert(a.l <= a.r);
    return a;
}

struct ST {
    std::vector<Cum> data;
    int size;

    ST(int n) {
        size = 1 << std::__lg(std::max(1, n - 1)) + 1;
        data.assign(size * 2, Cum());
    }

    void upd(int i, Cum mod) {
        data[i] = merge(data[i], mod);
    }

    void push(int i) {
        assert(i < size);

        upd(2 * i, data[i]);
        upd(2 * i + 1, data[i]);
        data[i].l = 0;
        data[i].r = inf;
    }

    void _update(int i, int l, int r, int ql, int qr, Cum mod) {
        if (qr <= l || r <= ql) {
            return;
        } else if (ql <= l && r <= qr) {
            upd(i, mod);
        } else {
            push(i);
            _update(2 * i, l, (l + r) / 2, ql, qr, mod);
            _update(2 * i + 1, (l + r) / 2, r, ql, qr, mod);
        }
    }

    void update(int l, int r, Cum mod) {
        _update(1, 0, size, l, r, mod);
    }

    std::vector<int> get() {
        for (int i = 1; i < size; i++) {
            push(i);
        }
        std::vector<int> res(size);
        for (int i = 0; i < size; i++) {
            res[i] = data[i + size].l;
            assert(data[i + size].l == data[i + size].r);
        }
        return res;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    ST st(n);
    for (int i = 0; i < k; i++) {
        int l = left[i];
        int r = right[i] + 1;
        assert(0 <= height[i] && height[i] < inf);
        Cum cum(0, inf);
        if (op[i] == 1) {
            cum.l = height[i];
        } else {
            cum.r = height[i];
        }
        st.update(l, r, cum);
    }

    auto ans = st.get();

    std::copy(ans.begin(), ans.begin() + n, finalHeight);

    return;
}