#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
struct node {
  int x, y;
} a[maxn];
int ans[maxn];
int f[maxn];
bool cmp(int c, int d) { return c < d; }
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &f[i]);
  }
  stack<int> s;
  node ff;
  ff.x = 0;
  ff.y = 0;
  s.push(0);
  a[0].y = 0;
  a[0].x = 0;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &a[i].x, &a[i].y);
  }
  for (int i = m; i >= 1; i--) {
    if (a[i].y > a[s.top()].y) {
      s.push(i);
    }
  }
  int flag = n;
  int kk = 0;
  int gg = a[s.top()].y;
  for (int i = gg + 1; i <= n; i++) ans[i] = f[i];
  sort(f + 1, f + 1 + gg);
  int l = 1;
  int r = gg;
  int per = s.top();
  s.pop();
  while (!s.empty()) {
    int now = s.top();
    s.pop();
    if (a[per].x == 1) {
      for (int i = a[per].y; i > a[now].y; i--) ans[i] = f[r--];
    } else {
      for (int i = a[per].y; i > a[now].y; i--) {
        ans[i] = f[l++];
      }
    }
    per = now;
  }
  for (int i = 1; i < n; i++) {
    printf("%d ", ans[i]);
  }
  printf("%d\n", ans[n]);
  return 0;
}
