#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m, a[200001], new_a[200001], i, j, t, r, beg, end;
  vector<pair<int, int> > ops, new_ops;
  ops.push_back(make_pair(0, 0));
  new_ops.push_back(make_pair(0, 0));
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &t, &r);
    ops.push_back(make_pair(t, r));
  }
  i = m;
  while (i >= 1) {
    new_ops.push_back(ops[i]);
    j = i - 1;
    while (j >= 1 && ops[j].second <= ops[i].second) {
      j--;
      continue;
    }
    i = j;
  }
  m = new_ops.size() - 1;
  for (i = new_ops[m].second + 1; i <= n; i++) {
    new_a[i] = a[i];
  }
  sort(a + 1, a + new_ops[m].second + 1);
  beg = 1;
  end = new_ops[m].second;
  for (i = m; i > 0; i--) {
    for (j = new_ops[i].second; j > new_ops[i - 1].second; j--) {
      if (new_ops[i].first == 1) {
        new_a[j] = a[end];
        end--;
      } else {
        new_a[j] = a[beg];
        beg++;
      }
    }
  }
  for (i = 1; i <= n; i++) printf("%d ", new_a[i]);
  printf("\n");
  return 0;
}
