#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int ff = 0x3f3f3f3f;
struct node {
  int d;
  int r;
  int pos;
} p[maxn];
int n, m;
int a[maxn];
int ans[maxn];
bool cmp3(struct node x, struct node y) {
  if (x.r != y.r) return x.r > y.r;
  return x.pos > y.pos;
}
bool cmp1(int x, int y) { return x < y; }
bool cmp2(int x, int y) { return x > y; }
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &p[i].d, &p[i].r);
    p[i].pos = i;
  }
  sort(p + 1, p + m + 1, cmp3);
  int o = -1;
  int cnt = n + 1;
  int l = 1, r = p[1].r;
  int c = p[1].d;
  int t = 1;
  int sum = p[1].r;
  for (int i = 1; i <= m; i++) {
    if (i == 1) {
      if (p[1].d == 1)
        sort(a + 1, a + p[i].r + 1, cmp1);
      else
        sort(a + 1, a + p[i].r + 1, cmp2);
      o = p[1].pos;
      continue;
    }
    if (p[i].pos <= o) continue;
    int tmp = sum - p[i].r;
    sum -= tmp;
    if (t % 2 == 1) {
      while (tmp--) ans[--cnt] = a[r--];
    } else {
      while (tmp--) ans[--cnt] = a[l++];
    }
    if (p[i].d != c) t++;
    c = p[i].d;
    o = p[i].pos;
  }
  if (l < r) {
    if (c == 1)
      sort(a + l, a + r + 1, cmp1);
    else
      sort(a + l, a + r + 1, cmp2);
  }
  for (int i = l; i <= r; i++) printf("%d ", a[i]);
  for (int i = cnt; i <= n; i++) printf("%d ", ans[i]);
  for (int i = p[1].r + 1; i <= n; i++) cout << a[i] << ' ';
  return 0;
}
