#include <bits/stdc++.h>
using namespace std;
struct query {
  int ind, t, r;
};
query q[200005];
int n, m, arr[200005], dp[200005], ans[200005];
set<int> s;
map<int, int> cnt;
bool comp(query a, query b) {
  if (a.r < b.r) return true;
  if (a.r > b.r) return false;
  return (a.ind < b.ind);
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
    s.insert(arr[i]);
    cnt[arr[i]]++;
  }
  for (int i = 1; i <= m; i++) {
    cin >> q[i].t >> q[i].r;
    q[i].ind = i;
  }
  sort(q + 1, q + m + 1, comp);
  dp[m] = m;
  for (int i = m - 1; i > 0; i--)
    if (q[i].ind > q[dp[i + 1]].ind)
      dp[i] = i;
    else
      dp[i] = dp[i + 1];
  int p = n;
  while (q[m].r < p) {
    cnt[arr[p]]--;
    if (cnt[arr[p]] == 0) s.erase(arr[p]);
    ans[p] = arr[p];
    p--;
  }
  int p2 = m;
  while (s.size()) {
    while (1) {
      if (p2 == 1) break;
      if (q[p2 - 1].r < p) break;
      p2--;
    }
    if (q[dp[p2]].t == 1) {
      ans[p] = *s.rbegin();
      cnt[*s.rbegin()]--;
      if (cnt[*s.rbegin()] == 0) s.erase(ans[p]);
    } else {
      ans[p] = *s.begin();
      cnt[*s.begin()]--;
      if (cnt[*s.begin()] == 0) s.erase(ans[p]);
    }
    p--;
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << " ";
  return 0;
}
