Wall IOI 2014

#include <bits/stdc++.h>

using namespace std;

struct SegTree {
    int Size;
    vector < pair < int , int > > Tree;
    vector < pair < bool , int > > lazy_min, lazy_max;

    void init(int N) {
        Size = 1;
        while(Size < N)
            Size <<= 1;
        Tree.assign((Size << 1) + 1, make_pair(INT_MAX, 0));
        lazy_min.assign((Size << 1) + 1, make_pair(false, INT_MAX));
        lazy_max.assign((Size << 1) + 1, make_pair(false, 0));
    }

    void propagate(int x, int lx, int rx) {
        if(lx == rx)
            return;
        if(lazy_min[x].first) {
            Tree[x << 1].first = min(Tree[x << 1].first, lazy_min[x].second);
            Tree[(x << 1) | 1].first = min(Tree[(x << 1) | 1].first, lazy_min[x].second);
            Tree[x << 1].second = min(Tree[x << 1].first, Tree[x << 1].second);
            Tree[(x << 1) | 1].second = min(Tree[(x << 1) | 1].first, Tree[(x << 1) | 1].second);
            lazy_min[x << 1].first = lazy_min[(x << 1) | 1].first = true;
            lazy_min[x << 1].second = min(lazy_min[x << 1].second, lazy_min[x].second);
            lazy_min[(x << 1) | 1].second = min(lazy_min[(x << 1) | 1].second, lazy_min[x].second);
            if(lazy_max[x << 1].first)
                lazy_max[x << 1].second = min(lazy_min[x << 1].second, lazy_max[x << 1].second);
            if(lazy_max[(x << 1) | 1].first)
                lazy_max[(x << 1) | 1].second = min(lazy_min[(x << 1) | 1].second, lazy_max[(x << 1) | 1].second);
            lazy_min[x] = make_pair(false, INT_MAX);
        }
        if(lazy_max[x].first) {
            Tree[x << 1].second = max(Tree[x << 1].second, lazy_max[x].second);
            Tree[(x << 1) | 1].second = max(Tree[(x << 1) | 1].second, lazy_max[x].second);
            Tree[x << 1].first = max(Tree[x << 1].first, Tree[x << 1].second);
            Tree[(x << 1) | 1].first = max(Tree[(x << 1) | 1].first, Tree[(x << 1) | 1].second);
            lazy_max[x << 1].first = lazy_max[(x << 1) | 1].first = true;
            lazy_max[x << 1].second = max(lazy_max[x << 1].second, lazy_max[x].second);
            lazy_max[(x << 1) | 1].second = max(lazy_max[(x << 1) | 1].second, lazy_max[x].second);
            if(lazy_min[x << 1].first)
                lazy_min[x << 1].second = max(lazy_min[x << 1].second, lazy_max[x << 1].second);
            if(lazy_min[(x << 1) | 1].first)
                lazy_min[(x << 1) | 1].second = max(lazy_min[(x << 1) | 1].second, lazy_max[(x << 1) | 1].second);
            lazy_max[x] = make_pair(false, 0);
        }
    }

    void maximize(int x, int lx, int rx, int st, int dr, int h) {
        propagate(x, lx, rx);
        if(st <= lx && rx <= dr) {
            Tree[x].second = max(Tree[x].second, h);
            Tree[x].first = max(Tree[x].first, Tree[x].second);
            lazy_max[x].first = true;
            lazy_max[x].second = max(lazy_max[x].second, h);
            return;
        }
        int mid = (lx + rx) >> 1;
        if(st <= mid)
            maximize(x << 1, lx, mid, st, dr, h);
        if(mid < dr)
            maximize((x << 1) | 1, mid + 1, rx, st, dr, h);
    }

    void minimize(int x, int lx, int rx, int st, int dr, int h) {
        propagate(x, lx, rx);
        if(st <= lx && rx <= dr) {
            Tree[x].first = min(Tree[x].first, h);
            Tree[x].second = min(Tree[x].second, Tree[x].first);
            lazy_min[x].first = true;
            lazy_min[x].second = min(lazy_min[x].second, h);
            return;
        }
        int mid = (lx + rx) >> 1;
        if(st <= mid)
            minimize(x << 1, lx, mid, st, dr, h);
        if(mid < dr)
            minimize((x << 1) | 1, mid + 1, rx, st, dr, h);
    }

    int query(int x, int lx, int rx, int poz) {
        propagate(x, lx, rx);
        if(lx == rx)
            return Tree[x].second;
        int mid = (lx + rx) >> 1;
        if(poz <= mid)
            return query(x << 1, lx, mid, poz);
        else
            return query((x << 1) | 1, mid + 1, rx, poz);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    SegTree Tree;
    Tree.init(N);
    while(Q--) {
        int type, st, dr, h;
        cin >> type >> st >> dr >> h;
        ++st, ++dr;
        if(type == 1)
            Tree.maximize(1, 1, N, st, dr, h);
        else
            Tree.minimize(1, 1, N, st, dr, h);
    }
    for(int i = 1; i <= N; ++i)
        cout << Tree.query(1, 1, N, i) << '\n';
}