#include <bits/stdc++.h>
using namespace std;
bool compare(int x, int y) {
  if (x > y) return true;
  return false;
}
bool comp(pair<int, pair<int, int>> x, pair<int, pair<int, int>> y) {
  if (x.first > y.first) return true;
  if (x.first == y.first && x.second.first < y.second.first) return true;
  return false;
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> input(n), ans;
  for (int i = 0; i < n; i++) cin >> input[i];
  vector<pair<int, pair<int, int>>> vec;
  for (int i = 0; i < m; i++) {
    int r, t;
    cin >> t >> r;
    vec.push_back({r - 1, {i, t}});
  }
  sort(vec.begin(), vec.end(), comp);
  int maxi = vec[0].second.first;
  int prer = vec[0].first;
  int pret = vec[0].second.second;
  sort(input.begin(), input.begin() + prer + 1);
  int start = 0;
  int end = prer;
  for (int i = n - 1; i > prer; i--) ans.push_back(input[i]);
  for (int i = 1; i < vec.size(); i++) {
    if (vec[i].second.first > maxi) {
      int count = -vec[i].first + prer;
      if (pret == 1) {
        for (; count > 0; count--) ans.push_back(input[end--]);
      } else {
        for (; count > 0; count--) ans.push_back(input[start++]);
      }
      pret = vec[i].second.second;
      prer = vec[i].first;
      maxi = vec[i].second.first;
    }
  }
  if (pret == 2) {
    sort(input.begin() + start, input.begin() + end + 1);
  } else {
    sort(input.begin() + start, input.begin() + end + 1, compare);
  }
  for (int i = start; i <= end; i++) {
    ans.push_back(input[i]);
  }
  for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << " ";
  return 0;
}
