#include <bits/stdc++.h>
using namespace std;
multiset<int> Set;
multiset<int>::iterator iter;
pair<int, int> b[250001], c[250001];
int a[250001], ans[250001], n, i, j, k, q;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (i = 1; i <= n; i++) {
    cin >> a[i];
    ans[i] = a[i];
  }
  for (i = 1; i <= q; i++) cin >> b[i].first >> b[i].second;
  k++;
  c[k] = b[q];
  for (i = q; i >= 1; i--)
    if (c[k].second < b[i].second) {
      k++;
      c[k] = b[i];
    }
  for (i = 1; i <= c[k].second; i++) Set.insert(a[i]);
  for (i = k; i >= 1; i--)
    if (c[i].first == 2) {
      for (j = c[i].second; j >= c[i - 1].second + 1; j--) {
        ans[j] = *Set.begin();
        Set.erase(Set.begin());
      }
    } else {
      for (j = c[i].second; j >= c[i - 1].second + 1; j--) {
        ans[j] = *Set.rbegin();
        iter = Set.end();
        iter--;
        Set.erase(iter);
      }
    }
  for (i = 1; i <= n; i++) cout << ans[i] << " ";
  cout << '\n';
  return 0;
}
