#include <bits/stdc++.h>
using namespace std;
stack<pair<int, int> > st, u;
int m, n, x, y, z, q;
int ara[300000];
multiset<int> nums;
int ans[300000];
int main() {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) scanf("%d", &ara[i]);
  for (int i = 0; i < q; i++) {
    scanf("%d %d", &x, &y);
    while (!st.empty()) {
      pair<int, int> temp = st.top();
      if (temp.second > y)
        break;
      else
        st.pop();
    }
    st.push(make_pair(x, y));
  }
  while (!st.empty()) {
    u.push(st.top());
    st.pop();
  }
  for (int i = 1; i <= u.top().second; i++) nums.insert(ara[i]);
  for (int i = u.top().second + 1; i <= n; i++) ans[i] = ara[i];
  while (u.size() != 1) {
    pair<int, int> temp = u.top();
    u.pop();
    pair<int, int> temp_2 = u.top();
    multiset<int>::iterator it, it_2;
    if (temp.first == 1) {
      it = nums.end();
      it--;
      for (int i = temp.second; i > temp_2.second; i--) {
        ans[i] = *it;
        it_2 = it;
        it--;
        nums.erase(it_2);
      }
    } else {
      it = nums.begin();
      for (int i = temp.second; i > temp_2.second; i--) {
        ans[i] = *it;
        it_2 = it;
        it++;
        nums.erase(it_2);
      }
    }
  }
  if (u.top().first == 1) {
    multiset<int>::iterator it = nums.end(), it_2;
    it--;
    for (int i = u.top().second; i > 0; i--) {
      ans[i] = *it;
      it_2 = it;
      it--;
      nums.erase(it_2);
    }
  } else {
    multiset<int>::iterator it = nums.begin(), it_2;
    for (int i = u.top().second; i > 0; i--) {
      ans[i] = *it;
      it_2 = it;
      it++;
      nums.erase(it_2);
    }
  }
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  return 0;
}
