#include <bits/stdc++.h>
using namespace std;
int a[200005], v[200005], aux[200005];
bool cmp(const pair<int, int> &i, const pair<int, int> &j) {
  return i.first > j.first;
}
bool cmp1(const int &i, const int &j) { return i > j; }
int main() {
  ios_base::sync_with_stdio(false);
  int n, m, t, idx;
  vector<pair<int, int> > vec;
  vector<pair<int, int> > vv;
  vector<int> ans;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) {
    cin >> t >> idx;
    idx--;
    v[i] = t;
    vec.push_back(make_pair(idx, i));
  }
  int maxval = -1;
  for (int i = m - 1; i >= 0; i--) {
    if (vec[i].first > maxval) {
      maxval = vec[i].first;
      aux[i] = i;
    } else
      aux[i] = aux[i + 1];
  }
  for (int i = 0; i < m; i++) {
    vv.push_back(make_pair(vec[aux[i]].first, v[aux[i]]));
  }
  if (vv[0].second == 1)
    sort(a, a + vv[0].first + 1);
  else
    sort(a, a + vv[0].first + 1, cmp1);
  int chk = vv[0].second, l = 0, r = vv[0].first, diff;
  for (int i = 0; i < (int)vv.size(); i++) {
    if (i + 1 < (int)vv.size())
      diff = vv[i].first - vv[i + 1].first;
    else
      diff = vv[i].first + 1;
    if (vv[i].second == chk) {
      while (diff > 0) {
        ans.push_back(a[r--]);
        diff--;
      }
    } else {
      while (diff > 0) {
        ans.push_back(a[l++]);
        diff--;
      }
    }
  }
  reverse(ans.begin(), ans.end());
  for (int i = vv[0].first + 1; i < n; i++) ans.push_back(a[i]);
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';
  cout << endl;
  return 0;
}
