#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = getchar();
  int s = 0, w = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = (s << 1) + (s << 3) + ch - 48;
    ch = getchar();
  }
  return s * w;
}
int n, m;
int num[200005];
int opt[200005];
int pos[200005];
int top, s[200005];
bool cmp(int a, int b) { return a > b; }
int ans[200005];
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) {
    num[i] = read();
  }
  for (int i = 1; i <= m; i++) {
    opt[i] = read();
    pos[i] = read();
  }
  for (int i = 1; i <= m; i++) {
    if (!top || pos[s[top]] > pos[i])
      s[++top] = i;
    else {
      while (top && pos[s[top]] <= pos[i]) top--;
      s[++top] = i;
    }
  }
  s[top + 1] = 0;
  int l = 1, r = n, now = n;
  while (r > pos[s[1]]) ans[now] = num[r], now--, r--;
  sort(num + 1, num + 1 + r);
  for (int i = 1; i <= top; i++) {
    for (int j = 1; j <= pos[s[i]] - pos[s[i + 1]]; j++) {
      if (opt[s[i]] == 1) {
        ans[now] = num[r];
        now--;
        r--;
      } else {
        ans[now] = num[l];
        now--;
        l++;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    printf("%d ", ans[i]);
  }
  return 0;
}
