#include <bits/stdc++.h>
using namespace std;
int a[200000];
pair<int, int> r[200002];
int main() {
  int n, m, x, y;
  stack<pair<int, int> > st;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &y, &x);
    while (!st.empty() && st.top().first <= x) st.pop();
    st.push(make_pair(x, y));
  }
  m = st.size();
  while (!st.empty()) {
    r[st.size() - 1] = st.top();
    st.pop();
  }
  r[m].first = 0;
  multiset<int> as;
  multiset<int, greater<int> > ds;
  vector<int> ans;
  for (int i = 0; i < r[0].first; i++) {
    as.insert(a[i]);
    ds.insert(a[i]);
  }
  for (int i = n - 1; i >= r[0].first; i--) ans.push_back(a[i]);
  for (int i = 0; i < m; i++) {
    if (r[i].second == 2) {
      int k = r[i].first - r[i + 1].first;
      while (k--) {
        ans.push_back(*as.begin());
        as.erase(as.begin());
      }
    } else {
      int k = r[i].first - r[i + 1].first;
      while (k--) {
        ans.push_back(*ds.begin());
        ds.erase(ds.begin());
      }
    }
  }
  while (!ans.empty()) {
    printf("%d ", ans.back());
    ans.pop_back();
  }
  return 0;
}
