#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
const int N = 2e5 + 5;
int a[N], b[N];
int r[N], t[N];
int main() {
  int n, m;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int top = 0;
    for (int i = 1; i <= m; i++) {
      scanf("%d%d", &t[i], &r[i]);
      while (top && r[i] > r[top]) top--;
      top++;
      t[top] = t[i];
      r[top] = r[i];
    }
    for (int i = r[1] + 1; i <= n; i++) b[i] = a[i];
    sort(a + 1, a + r[1] + 1);
    int L = 1, R = r[1];
    for (int i = 1; i < top; i++) {
      for (int j = r[i]; j > r[i + 1]; j--) {
        if (t[i] == 1)
          b[j] = a[R--];
        else
          b[j] = a[L++];
      }
    }
    for (int i = r[top]; i >= 1; i--) {
      if (t[top] == 1)
        b[i] = a[R--];
      else
        b[i] = a[L++];
    }
    for (int i = 1; i <= n; i++) printf("%d%c", b[i], (i == n) ? '\n' : ' ');
  }
  return 0;
}
