#include <bits/stdc++.h>

#define debug(...) fprintf(stderr, __VA_ARGS__)

using i64 = long long;

constexpr int N = 2e5 + 5, INF = 0x3f3f3f3f;

void optimize() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

int a[N];
struct {
    int l, r, v, cov;
} tr[N * 4];

#define ls(x) (x * 2)
#define rs(x) (x * 2 + 1)

void pushup(int x) {
    tr[x].v = std::max(tr[ls(x)].v, tr[rs(x)].v);
}

void build(int l, int r, int x = 1) {
    tr[x] = {l, r, a[l], 0};
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, ls(x));
    build(mid + 1, r, rs(x));
    pushup(x);
}

void update(int x, int v, bool flag = true) {
    if (v < tr[x].cov) {
        return;
    }
    if (flag) {
        tr[x].cov = v;
        tr[x].v = v + 1;
    } else {
        tr[x].cov = tr[x].v = v;
    }
}

void pushdown(int x) {
    if (tr[x].cov) {
        int v1 = tr[ls(x)].v, v2 = tr[rs(x)].v;
        update(ls(x), tr[x].cov, tr[x].v > tr[x].cov && v1 >= v2);
        update(rs(x), tr[x].cov, tr[x].v > tr[x].cov && v2 >= v1);
        tr[x].cov = 0;
    }
}

void modify(int l, int r, int v, int x = 1) {
    if (l <= tr[x].l && tr[x].r <= r) {
        update(x, v, tr[x].v == v);
        return;
    }
    pushdown(x);
    int mid = (tr[x].l + tr[x].r) / 2;
    if (l <= mid) {
        modify(l, r, v, ls(x));
    }
    if (r > mid) {
        modify(l, r, v, rs(x));
    }
    pushup(x);
}

int query(int l, int r, int x = 1) {
    if (l <= tr[x].l && tr[x].r <= r) {
        return tr[x].v;
    }
    pushdown(x);
    int mid = (tr[x].l + tr[x].r) / 2;
    if (l > mid) {
        return query(l, r, rs(x));
    } else if (r <= mid) {
        return query(l, r, ls(x));
    } else {
        return std::max(query(l, r, ls(x)), query(l, r, rs(x)));
    }
}

void pushall(int x = 1) {
    if (tr[x].l == tr[x].r) {
        printf("%d ", tr[x].v);
        return;
    }
    pushdown(x);
    pushall(ls(x));
    pushall(rs(x));
}

int main(void) {
    // optimize();
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    build(1, n);
    for (int i = 1, l, r; i <= m; ++i) {
        scanf("%d%d", &l, &r);
        int mx = query(l, r);
        modify(l, r, mx);
    }
    pushall();
    return 0;
}