#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
int read() {
  char c = getchar();
  int re = 0, f = 1;
  while (c<'0' | c> '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    re = re * 10 + c - '0';
    c = getchar();
  }
  return re * f;
}
int a[200010], b[200010];
struct node {
  int t, r;
} op[200010];
int main() {
  int n = read(), k = read();
  for (int i = 1; i <= n; i++) a[i] = read(), b[i] = a[i];
  int siz = 0;
  for (int i = 1; i <= k; i++) {
    int o = read(), p = read();
    for (int j = siz; j > 0; j--) {
      if (op[siz].r <= p)
        siz--;
      else
        break;
    }
    op[++siz].t = o, op[siz].r = p;
  }
  int m = op[1].r, l = 1;
  sort(b + 1, b + 1 + m);
  for (int i = 1; i < siz; i++) {
    for (int j = op[i].r; j > op[i + 1].r; j--) {
      if (op[i].t == 1) {
        a[j] = b[m--];
      } else {
        a[j] = b[l++];
      }
    }
  }
  for (int j = op[siz].r; j >= 1; j--)
    if (op[siz].t == 1) {
      a[j] = b[m--];
    } else {
      a[j] = b[l++];
    }
  for (int i = 1; i <= n; i++) {
    printf("%d ", a[i]);
  }
  return 0;
}
