#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
const int maxn = 200005;
void task() {
  int n, m, last, t, r;
  cin >> n >> m;
  vector<int> a(n);
  multiset<int> s;
  for (int i = 0; i < n; i++) cin >> a[i];
  deque<pair<int, int> > q;
  for (int i = 0; i < m; i++) {
    cin >> t >> r;
    while (!q.empty() and q.back().first < r) {
      q.pop_back();
    }
    q.push_back(make_pair(r, t));
  }
  int v = q.front().first;
  for (int i = 0; i < v; i++) {
    s.insert(a[i]);
  }
  m = q.size();
  vector<int> ans(v);
  for (int i = 0; i < m; i++) {
    pair<int, int> qe = q.front();
    q.pop_front();
    r = qe.first;
    t = qe.second;
    if (i == m - 1)
      last = 0;
    else
      last = q.front().first;
    if (t == 1) {
      for (int j = r - 1; j >= last; j--) {
        ans[j] = *s.rbegin();
        s.erase(--s.end());
      }
    } else {
      for (int j = r - 1; j >= last; j--) {
        ans[j] = *s.begin();
        s.erase(s.begin());
      }
    }
  }
  int rest = ans.size();
  while (rest < n) {
    ans.push_back(a[rest++]);
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << ' ';
  }
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T = 1;
  while (T--) {
    task();
  }
  return 0;
}
