#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> v(n), ans(n, -1);
  deque<pair<int, int> > s;
  deque<int> dq;
  for (int i = 0; i < n; ++i) scanf("%d", &v[i]);
  for (int i = 0; i < m; ++i) {
    int t, r;
    scanf("%d%d", &t, &r);
    while (!s.empty() && s.back().first <= r) s.pop_back();
    s.push_back({r, t});
  }
  int k = n;
  while (k > s[0].first) ans[k - 1] = v[k - 1], --k;
  for (int i = 0; i < s[0].first; ++i) dq.push_back(v[i]);
  sort(dq.begin(), dq.end());
  for (int i = 0; i < s.size(); ++i) {
    if (i) {
      int l = s[i - 1].first - 1;
      while (l > s[i].first) {
        if (s[i - 1].second == 1) {
          ans[l - 1] = dq.back();
          dq.pop_back();
        } else {
          ans[l - 1] = dq.front();
          dq.pop_front();
        }
        --l;
      }
    }
    if (s[i].second == 1) {
      ans[s[i].first - 1] = dq.back();
      dq.pop_back();
    } else {
      ans[s[i].first - 1] = dq.front();
      dq.pop_front();
    }
  }
  k = s.back().first - 1;
  while (k > 0) {
    if (s.back().second == 1) {
      ans[k - 1] = dq.back();
      dq.pop_back();
    } else {
      ans[k - 1] = dq.front();
      dq.pop_front();
    }
    --k;
  }
  for (int i = 0; i < n; ++i) printf("%d ", ans[i]);
  puts("");
  return 0;
}
