#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int r[N], t[N];
int a[N], b[N];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  int tot = 0;
  for (int i = 0; i < m; i++) {
    int rr, tt;
    scanf("%d%d", &tt, &rr);
    while (tot > 0 && r[tot - 1] <= rr) tot--;
    if (tot == 0 || t[tot - 1] != tt) {
      r[tot++] = rr;
      t[tot - 1] = tt;
    }
  }
  for (int i = r[0] + 1; i <= n; i++) b[i] = a[i];
  sort(a + 1, a + 1 + r[0]);
  int ll = 1, rr = r[0];
  for (int i = 0; i < tot; i++) {
    int len;
    if (i == tot - 1)
      len = r[i];
    else
      len = r[i] - r[i + 1];
    if (t[i] == 1) {
      for (int j = r[i]; j > r[i] - len; j--) b[j] = a[rr - r[i] + j];
      rr -= len;
    } else {
      for (int j = r[i]; j > r[i] - len; j--) b[j] = a[ll + r[i] - j];
      ll += len;
    }
  }
  for (int i = 1; i <= n; i++) printf("%d ", b[i]);
  printf("\n");
  return 0;
}
