#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-16;
const int N = 200009;
const int inf = (int)1e9;
const int mod = (int)1e9 + 7;
struct quest {
  int r, t, i;
  bool friend operator<(quest a, quest b) {
    return a.r == b.r ? a.t < b.t : a.r < b.r;
  }
} q[N];
int a[N];
int ans[N];
multiset<int> s;
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &q[i].t, &q[i].r);
    q[i].i = i;
  }
  sort(q + 1, q + m + 1);
  for (int i = 1; i <= q[m].r; i++) {
    s.insert(a[i]);
  }
  int pos = q[m].r;
  int ind = q[m].i;
  int type = q[m].t;
  for (int i = m; i >= 1; i--) {
    if (q[i].i > ind) {
      type = q[i].t;
      ind = q[i].i;
    }
    while ((pos > 0 && i <= 1) || (pos > q[i - 1].r && i >= 2)) {
      if (type == 1) {
        ans[pos] = *(--s.end());
        s.erase(--s.end());
      } else {
        ans[pos] = *s.begin();
        s.erase(s.begin());
      }
      pos--;
    }
  }
  for (int i = 1; i <= n; i++) {
    printf("%d%c", i <= q[m].r ? ans[i] : a[i], " \n"[i == n]);
  }
  return 0;
}
