#include <bits/stdc++.h>
using namespace std;
const int M = 1e6;
long long n, q, a[M], segmin[M], segmax[M];
long long type[M], qr[M], mxq[M];
long long lastq;
bool f;
void build(long long st, long long en, long long tag) {
  segmin[tag] = st;
  segmax[tag] = st;
  if (st + 1 == en) {
    return;
  }
  long long mid = (st + en) >> 1;
  build(st, mid, tag * 2);
  build(mid, en, tag * 2 + 1);
}
void updatemax(long long st, long long en, long long tag, long long pos,
               long long val) {
  if (st + 1 == en) {
    segmax[tag] = pos;
    return;
  }
  long long mid = (st + en) >> 1, tl = tag * 2, tr = tl + 1;
  if (pos < mid)
    updatemax(st, mid, tl, pos, val);
  else
    updatemax(mid, en, tr, pos, val);
  if (a[segmax[tag]] < a[segmax[tl]]) segmax[tag] = segmax[tl];
  if (a[segmax[tag]] < a[segmax[tr]]) segmax[tag] = segmax[tr];
}
long long getmax(long long st, long long en, long long tag, long long lo,
                 long long hi) {
  if (en <= lo || hi <= st) return 0;
  if (lo <= st && en <= hi) {
    return segmax[tag];
  }
  long long mid = (st + en) >> 1, tl = tag * 2, tr = tl + 1;
  long long lans = getmax(st, mid, tl, lo, hi);
  long long rans = getmax(mid, en, tr, lo, hi);
  if (a[lans] <= a[rans]) {
    return rans;
  }
  return lans;
}
void updatemin(long long st, long long en, long long tag, long long pos,
               long long val) {
  if (st + 1 == en) {
    segmin[tag] = pos;
    return;
  }
  long long mid = (st + en) >> 1, tl = tag * 2, tr = tl + 1;
  if (pos < mid)
    updatemin(st, mid, tl, pos, val);
  else
    updatemin(mid, en, tr, pos, val);
  if (a[segmin[tl]] < a[segmin[tag]]) segmin[tag] = segmin[tl];
  if (a[segmin[tr]] < a[segmin[tag]]) segmin[tag] = segmin[tr];
}
long long getmin(long long st, long long en, long long tag, long long lo,
                 long long hi) {
  if (en <= lo || hi <= st) return n + 1;
  if (lo <= st && en <= hi) {
    return segmin[tag];
  }
  long long mid = (st + en) >> 1, tl = tag * 2, tr = tl + 1;
  long long lans = getmin(st, mid, tl, lo, hi);
  long long rans = getmin(mid, en, tr, lo, hi);
  if (a[rans] <= a[lans])
    return rans;
  else
    return lans;
}
void print(long long st, long long en, long long tag) {
  cout << st << ' ' << en - 1 << ' ' << a[segmax[tag]] << endl;
  if (st + 1 == en) {
    return;
  }
  long long mid = (st + en) >> 1, tl = tag * 2, tr = tl + 1;
  print(st, mid, tl);
  print(mid, en, tr);
}
int main(int argc, char** argv) {
  cin >> n >> q;
  a[n + 1] = 1e18;
  a[0] = -1e18;
  build(1, n + 1, 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    updatemax(1, n + 1, 1, i, a[i]);
    updatemin(1, n + 1, 1, i, a[i]);
  }
  for (int i = 1; i <= q; i++) {
    cin >> type[i] >> qr[i];
  }
  for (int i = q; i; i--) {
    mxq[i] = qr[mxq[i + 1]] < qr[i] ? i : mxq[i + 1];
  }
  lastq = mxq[1];
  while (lastq != q) {
    long long nowq = mxq[lastq + 1];
    long long lastr = qr[lastq], nowr = qr[nowq];
    long long pos = lastr;
    if (type[lastq] == 1) {
      while (nowr < pos) {
        long long mxpos = getmax(1, n + 1, 1, 1, pos + 1);
        long long mx = a[mxpos], tmp = a[pos];
        swap(a[pos], a[mxpos]);
        updatemax(1, n + 1, 1, pos, mx);
        updatemax(1, n + 1, 1, mxpos, tmp);
        updatemin(1, n + 1, 1, pos, mx);
        updatemin(1, n + 1, 1, mxpos, tmp);
        pos--;
      }
    } else {
      while (nowr < pos) {
        long long mnpos = getmin(1, n + 1, 1, 1, pos + 1);
        long long mn = a[mnpos], tmp = a[pos];
        swap(a[pos], a[mnpos]);
        updatemin(1, n + 1, 1, pos, mn);
        updatemin(1, n + 1, 1, mnpos, tmp);
        updatemax(1, n + 1, 1, pos, mn);
        updatemax(1, n + 1, 1, mnpos, tmp);
        pos--;
      }
    }
    lastq = nowq;
  }
  sort(a + 1, a + 1 + qr[lastq]);
  if (type[lastq] == 2) {
    reverse(a + 1, a + 1 + qr[lastq]);
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << ' ';
  }
  cout << '\n';
  return 0;
}
