#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], ans[N], idx[N], typ[N];
inline int read() {
  int sum = 0, ff = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') ff = -1;
    ch = getchar();
  }
  while (isdigit(ch)) sum = sum * 10 + (ch ^ 48), ch = getchar();
  return sum * ff;
}
int main() {
  int n, m;
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  int mx = 0;
  for (int i = 1; i <= m; i++) {
    int t, r;
    t = read();
    r = read();
    idx[r] = i;
    typ[r] = t;
    mx = max(mx, r);
  }
  sort(a + 1, a + mx + 1);
  int flag, now = 0, hh = 1, tt = mx;
  for (int i = mx; i; i--) {
    if (now < idx[i]) {
      now = idx[i];
      flag = typ[i];
    }
    if (flag == 1)
      ans[i] = a[tt--];
    else
      ans[i] = a[hh++];
  }
  for (int i = 1; i <= mx; i++) printf("%d ", ans[i]);
  for (int i = mx + 1; i <= n; i++) printf("%d ", a[i]);
  return 0;
}
