#include <bits/stdc++.h>
using namespace std;
int a[200005], c[200005], b[200005], ans[200005];
struct node {
  int x, y;
} e[200005];
int main() {
  int n, m, Max = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &e[i].x, &e[i].y);
  }
  int p = 0, cnt = 1;
  for (int i = m; i >= 1; i--) {
    if (e[i].y > p) {
      c[cnt] = e[i].x;
      b[cnt++] = e[i].y;
      p = e[i].y;
    }
  }
  sort(a + 1, a + b[cnt - 1] + 1);
  int l = 1, r = n, f = 1;
  p = 0;
  for (; r > b[cnt - 1]; r--) ans[p++] = a[r];
  for (int i = cnt - 1; i > 0; i--) {
    int x = b[i] - b[i - 1];
    if (f == c[i]) {
      while (x--) {
        ans[p++] = a[r--];
      }
    } else {
      while (x--) {
        ans[p++] = a[l++];
      }
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    printf("%d ", ans[i]);
  }
  printf("\n");
}
