#include <bits/stdc++.h>
using namespace std;
queue<int> inc;
queue<int> deec;
int a[200005];
int b[200005];
pair<int, int> xx[200005];
vector<int> res;
int main() {
  int n, m, ti, r;
  scanf("%d", &n);
  scanf("%d", &m);
  int i;
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  int _max = -1;
  for (i = 1; i <= m; i++) {
    scanf("%d", &ti);
    scanf("%d", &r);
    _max = max(_max, r);
    r--;
    xx[r].first = ti;
    xx[r].second = i;
  }
  sort(b, b + _max);
  for (i = 0; i < _max; i++) inc.push(b[i]);
  for (i = _max - 1; i >= 0; i--) deec.push(b[i]);
  int now = 0, tp, ac = 0;
  for (i = n - 1; i >= 0; i--) {
    if (xx[i].first == 0 && ac == 0) {
      res.push_back(a[i]);
    } else {
      if (xx[i].second > now) {
        now = xx[i].second;
        ac = xx[i].first;
      }
      if (ac == 1) {
        tp = deec.front();
        deec.pop();
        res.push_back(tp);
      } else {
        tp = inc.front();
        inc.pop();
        res.push_back(tp);
      }
    }
  }
  for (i = n - 1; i >= 0; i--) printf("%d ", res[i]);
  puts("");
  return 0;
}
