#include <bits/stdc++.h>
using namespace std;
int n, op, p;
int a[200005], out[200005];
struct dosth {
  int t, r;
} o[200005];
int way;
bool cmp(int a, int b) {
  if (way == 1)
    return a < b;
  else
    return a > b;
}
int main() {
  scanf("%d%d", &n, &op);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  if (op == 0) {
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    return 0;
  }
  for (int i = 1; i <= op; i++) scanf("%d%d", &o[i].t, &o[i].r);
  p = 1;
  for (int i = 2; i <= op; i++) {
    while (p > 0 && o[i].r >= o[p].r) p--;
    o[++p] = o[i];
  }
  op = 1;
  for (int i = 2; i <= p; i++) {
    if (o[i].t != o[i - 1].t) o[++op] = o[i];
  }
  way = o[1].t;
  sort(a + 1, a + o[1].r + 1, cmp);
  for (int i = 1; i <= n; i++) out[i] = a[i];
  int p1 = 1, p2 = o[1].r;
  o[op + 1].r = 0;
  for (int i = 1; i <= op; i++) {
    for (int j = o[i].r; j > o[i + 1].r; j--) {
      if (!(i & 1)) {
        out[j] = a[p1++];
      } else {
        out[j] = a[p2--];
      }
    }
  }
  for (int i = 1; i <= n; i++) printf("%d ", out[i]);
  return 0;
}
