#include <bits/stdc++.h>
using namespace std;
int n, m, a[200020], ans[200020], cnt, hi;
pair<int, pair<int, int> > q[200020], rq[200020];
bool cmp(int a, int b) { return a > b; }
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0, x, y; i < m; i++) cin >> x >> y, q[i] = {y, {i, x}};
  sort(q, q + m);
  rq[cnt++] = q[m - 1];
  for (int i = m - 2; i >= 0; i--)
    if (rq[cnt - 1].second.first < q[i].second.first) rq[cnt++] = q[i];
  hi = rq[0].first;
  for (int i = hi; i < n; i++) ans[i] = a[i];
  sort(a, a + hi);
  int l = 0, r = hi - 1;
  for (int i = 0; i < cnt; i++) {
    if (rq[i].second.second == 1)
      for (int j = rq[i].first - 1; j >= rq[i + 1].first; j--) ans[j] = a[r--];
    else
      for (int j = rq[i].first - 1; j >= rq[i + 1].first; j--) ans[j] = a[l++];
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
}
