#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
struct Op {
  int r;
  int first;
  Op(int r, int first) {
    this->r = r;
    this->first = first;
  }
};
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector<int> vals(n);
  for (__typeof(vals.begin()) val = vals.begin(); val != vals.end(); ++val)
    scanf("%d", val);
  deque<Op> d;
  while (m--) {
    int r, first;
    scanf("%d %d", &r, &first);
    while ((!d.empty()) and (d.back().first <= first)) {
      d.pop_back();
    }
    d.push_back(Op(r, first));
  }
  vector<int> s_arr(vals.begin(), vals.begin() + d.front().first);
  sort(s_arr.begin(), s_arr.end());
  int i = 0, j = s_arr.size() - 1;
  int curr_r = d.front().r;
  int pos = j;
  while (pos >= 0) {
    if ((!d.empty()) and (pos == d.front().first - 1)) {
      curr_r = d.front().r;
      d.pop_front();
    }
    if (curr_r == 1) {
      vals[pos--] = s_arr[j--];
    } else {
      vals[pos--] = s_arr[i++];
    }
  }
  for (int idx = 0; idx < vals.size(); ++idx) {
    if (idx) printf(" ");
    printf("%d", vals[idx]);
  }
  printf("\n");
  return 0;
}
