#include <bits/stdc++.h>
using namespace std;
long long ar[200010], ad[200010], ans[200010], tm[200010], br[200010];
int main() {
  ios::sync_with_stdio(false);
  memset(ad, 0, sizeof(ad));
  memset(tm, 0, sizeof(tm));
  long long i, j, x, y, n, m, a, b, mx = -1, c = 1, t = -1;
  cin >> n >> m;
  for (i = 0; i < n; i++) {
    cin >> ar[i];
    br[i] = ar[i];
  }
  for (i = 0; i < m; i++) {
    cin >> a >> b;
    ad[b - 1] = a;
    tm[b - 1] = i + 1;
    mx = max(mx, b);
  }
  sort(ar, ar + mx);
  a = 0;
  b = mx - 1;
  for (i = b; i >= 0; i--) {
    if (tm[i] > t) {
      c = ad[i];
      t = tm[i];
    }
    if (c == 2) {
      ans[i] = ar[a];
      a++;
    } else {
      ans[i] = ar[b];
      b--;
    }
  }
  for (i = 0; i < mx; i++) cout << ans[i] << ' ';
  for (i = mx; i < n; i++) cout << br[i] << ' ';
  return 0;
}
