#include <bits/stdc++.h>
using ::std::cin;
using ::std::cout;
using ::std::endl;
using ::std::multiset;
using ::std::pair;
using ::std::vector;
int main() {
  ::std::ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  vector<pair<int, int>> tr;
  for (int i = 0; i < m; ++i) {
    int t, r;
    cin >> t >> r;
    while (!tr.empty() && tr.back().second <= r) tr.pop_back();
    tr.push_back({t, r});
  }
  tr.push_back({-1, 0});
  multiset<int> s;
  for (int i = 0; i < tr[0].second; ++i) s.insert(a[i]);
  for (int i = 0; i < static_cast<int>(tr.size()); ++i) {
    for (int j = tr[i].second - 1; j >= tr[i + 1].second; --j) {
      if (tr[i].first == 2) {
        a[j] = *s.begin();
        s.erase(s.begin());
      } else {
        a[j] = *--s.end();
        s.erase(--s.end());
      }
    }
  }
  for (int x : a) cout << x << " ";
  cout << endl;
  return 0;
}
