#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 1;
struct Node {
  int x, p;
  Node() {}
  Node(int P, int X) { p = P, x = X; }
} q[maxn];
int a[maxn];
int b[maxn];
int main() {
  int n, m, num, x, p, fir, end;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  num = 0;
  while (m--) {
    scanf("%d%d", &p, &x);
    while (num && x >= q[num].x) --num;
    if (p != q[num].p) q[++num] = Node(p, x);
  }
  q[num + 1].x = -1;
  for (int i = n - 1; i >= q[1].x; i--) b[i] = a[i];
  sort(a, a + q[1].x);
  end = 0;
  fir = q[1].x - 1;
  for (int i = 1; i <= num; i++) {
    if (q[i].p == 1) {
      for (int j = q[i].x - 1; j >= q[i + 1].x; j--) b[j] = a[j + end];
      fir -= q[i].x - q[i + 1].x;
    } else {
      for (int j = q[i].x - 1; j >= q[i + 1].x; j--) b[j] = a[fir - j];
      end += q[i].x - q[i + 1].x;
    }
  }
  for (int i = 0; i < n; i++) printf("%d ", b[i]);
  return 0;
}
