#include <bits/stdc++.h>
using namespace std;
int main() {
  int i;
  int n, m1;
  cin >> n >> m1;
  int a[n + 1];
  for (i = 1; i <= n; i++) cin >> a[i];
  int t, r;
  stack<pair<int, int> > s;
  pair<int, int> use;
  for (i = 1; i <= m1; i++) {
    cin >> t >> r;
    while (!s.empty() && (s.top().second <= (r))) {
      s.pop();
    }
    if (!s.empty() && (s.top().second > r && s.top().first == t)) continue;
    s.push(make_pair(t, r));
  }
  int prev = 0;
  vector<pair<int, int> > m;
  while (!s.empty()) {
    m.push_back(s.top());
    s.pop();
  }
  int size = m.size();
  set<pair<int, int> > s1, s2;
  for (i = 1; i <= m[size - 1].second; i++) {
    s1.insert(make_pair(-a[i], i));
    s2.insert(make_pair(a[i], i));
  }
  int r_end;
  pair<int, int> num;
  for (i = size - 1; i >= 0; i--) {
    r = m[i].second;
    if (i)
      r_end = m[i - 1].second;
    else
      r_end = 0;
    t = m[i].first;
    if (t == 1) {
      for (int j = r; j > r_end; j--) {
        num = *(s1.begin());
        s1.erase(num);
        s2.erase(make_pair(-num.first, num.second));
        a[j] = -num.first;
      }
    } else {
      for (int j = r; j > r_end; j--) {
        num = *(s2.begin());
        s2.erase(num);
        s1.erase(make_pair(-num.first, num.second));
        a[j] = num.first;
      }
    }
  }
  for (i = 1; i <= n; i++) cout << a[i] << " ";
  return 0;
}
