//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "wall.h"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
pair<int, int> minka(pair<int, int> a, pair<int, int> b) {
    if (a > b)
        swap(a, b);
    return {a.first, min(a.second, b.first)};
}
pair<int, int> maxka(pair<int, int> a, pair<int, int> b) {
    if (a < b)
        swap(a, b);
    return {a.first, max(a.second, b.first)};
}
struct segtree {
    int sz = 1;
    vector<int> tree;
    vector<int> tlkmn, tlkmx;
    void init(int n) {
        while (sz < n)
            sz *= 2;
        tree.assign(sz * 2, {});
        tlkmn.assign(sz * 2, 1e6);
        tlkmx.assign(sz * 2, 0);
    }
    void push(int v) {
        tlkmx[v * 2] = max(tlkmx[v], tlkmx[v * 2]);
        if (tlkmn[v * 2] < tlkmx[v * 2]) {
            tlkmn[v * 2] = tlkmx[v * 2];
        }
        tlkmx[v * 2 + 1] = max(tlkmx[v], tlkmx[v * 2 + 1]);
        if (tlkmn[v * 2 + 1] < tlkmx[v * 2 + 1]) {
            tlkmn[v * 2 + 1] = tlkmx[v * 2 + 1];
        }
        tlkmn[v * 2] = min(tlkmn[v], tlkmn[v * 2]);
        if (tlkmn[v * 2] < tlkmx[v * 2]) {
            tlkmx[v * 2] = tlkmn[v * 2];
        }
        tlkmn[v * 2 + 1] = min(tlkmn[v], tlkmn[v * 2 + 1]);
        if (tlkmn[v * 2 + 1] < tlkmx[v * 2 + 1]) {
            tlkmx[v * 2 + 1] = tlkmn[v * 2 + 1];
        }
        tlkmx[v] = 0;
        tlkmn[v] = 0;
    }
    void updmn(int v, int c) {
        if (tlkmx[v] > c) {
            tlkmx[v] = c;
        }
        tlkmn[v] = c;
    }
    void updmx(int v, int c) {
        if (tlkmn[v] < c) {
            tlkmn[v] = c;
        }
        tlkmx[v] = c;
    }
    void updmxseg(int l, int r, int v, int ll, int rr, int c) {
        if (ll <= l and r <= rr) {
            return updmx(v, c);
        }
        if (ll >= r and l >= rr) {
            return;
        }
        int m = l + r >> 1;
        push(v);
        updmxseg(l, m, v * 2, ll, rr, c);
        updmxseg(m, r, v * 2 + 1, ll, rr, c);
    }
    void updmnseg(int l, int r, int v, int ll, int rr, int c) {
        if (ll <= l and r <= rr) {
            return updmn(v, c);
        }
        if (ll >= r and l >= rr) {
            return;
        }
        int m = l + r >> 1;
        push(v);
        updmnseg(l, m, v * 2, ll, rr, c);
        updmnseg(m, r, v * 2 + 1, ll, rr, c);
    }
    void updmnseg(int l, int r, int c) {
        return updmnseg(0, sz, 1, l, r, c);
    }
    void updmxseg(int l, int r, int c) {
        return updmxseg(0, sz, 1, l, r, c);
    }
    int getv(int l, int r, int v, int ll, int rr) {
        if (ll <= l and r <= rr) {
            return tlkmn[v];
        }
        if (ll >= r and l >= rr) {
            return 0;
        }
        int m = l + r >> 1;
        push(v);
        return getv(l, m, v * 2, ll, rr) + getv(m, r, v * 2 + 1, ll, rr);
    }
    int getv(int v) {
        return getv(0, sz, 1, v, v + 1);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    segtree sg;
    sg.init(n);
    for (int i = 0; i < k; ++i) {
        if (op[i] == 1)
            sg.updmxseg(left[i], right[i]+1, height[i]);
        else
            sg.updmnseg(left[i], right[i]+1, height[i]);
    }
    for (int i = 0; i < n; ++i) {
        finalHeight[i] = sg.getv(i);
    }
}

/*
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;

}
 */