#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
void Never_give_up() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  set<pair<int, int> > qs;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> y >> x;
    while (!qs.empty() && qs.begin()->first <= x) {
      qs.erase(qs.begin());
    }
    qs.insert(make_pair(x, y));
  }
  multiset<int> s;
  int rg = qs.rbegin()->first;
  for (int i = 0; i < rg; i++) s.insert(a[i]);
  while (!qs.empty()) {
    int r = qs.rbegin()->first;
    int f = qs.rbegin()->second;
    qs.erase(*qs.rbegin());
    int l = 0;
    if (!qs.empty()) l = qs.rbegin()->first;
    for (int i = r - 1; i >= l; i--) {
      if (f == 1) a[i] = *s.rbegin();
      if (f == 2) a[i] = *s.begin();
      s.erase(s.find(a[i]));
    }
  }
  for (int i = 0; i < n; i++) cout << a[i] << ' ';
  puts("");
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tc = 1;
  for (int iTest = 0; iTest < tc; ++iTest) {
    Never_give_up();
  }
  return 0;
}
