#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int N, M;
int A[MAXN];
int B[MAXN][2];
int sz = 0;
vector<int> ans;
int main() {
  ios::sync_with_stdio(0);
  cin >> N >> M;
  set<pair<int, int> > st;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    st.insert(make_pair(A[i], i));
  }
  for (int i = 0, t, r; i < M; i++) {
    cin >> t >> r;
    while (sz > 0 && r >= B[sz - 1][1]) sz--;
    B[sz][0] = t;
    B[sz][1] = r;
    sz++;
  }
  int cur = 0, j = N;
  for (int i = 0; i < sz; i++) {
    while (j >= 1 && j > B[i][1]) {
      if (cur == 0) {
        ans.push_back(A[j]);
        st.erase(make_pair(A[j], j));
      } else if (cur == 1) {
        ans.push_back((--st.end())->first);
        st.erase(--st.end());
      } else {
        ans.push_back(st.begin()->first);
        st.erase(st.begin());
      }
      j--;
    }
    cur = B[i][0];
  }
  while (j >= 1) {
    if (cur == 0) {
      ans.push_back(A[j]);
      st.erase(make_pair(A[j], j));
    } else if (cur == 1) {
      ans.push_back((--st.end())->first);
      st.erase(--st.end());
    } else {
      ans.push_back(st.begin()->first);
      st.erase(st.begin());
    }
    j--;
  }
  for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << " ";
  return 0;
}
