#include <bits/stdc++.h>
using namespace std;
class e {
 public:
  int i, donde, tipo;
};
bool operator<(e a, e b) {
  return a.donde > b.donde || (a.donde == b.donde && a.i < b.i);
}
e com[200010];
int arr[200100], mx = -1, res[200100], k, l, dif, voy, r, val;
int main() {
  std::ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> arr[i];
  for (int i = 0; i < m; i++) {
    cin >> com[i].tipo >> com[i].donde;
    if (com[i].donde > mx) mx = com[i].donde;
    com[i].i = i;
  }
  sort(arr + 1, arr + mx + 1);
  for (int i = mx + 1; i <= n; i++) res[i] = arr[i];
  sort(com, com + m);
  r = mx;
  val = com[0].donde;
  int cont = 0;
  k = 1;
  l = mx;
  dif = com[0].tipo;
  voy = com[0].i;
  for (int i = 1; i < m; i++) {
    if (com[i].i > voy && com[i].tipo != dif) {
      dif = com[i].tipo;
      voy = com[i].i;
      cont = 0;
      if (dif == 1) {
        for (; cont < val - com[i].donde; k++) {
          cont++;
          res[r] = arr[k];
          r--;
        }
      } else {
        for (; cont < val - com[i].donde; l--) {
          cont++;
          res[r] = arr[l];
          r--;
        }
      }
      val = com[i].donde;
    } else if (com[i].i > voy && com[i].tipo == dif)
      voy = com[i].i;
  }
  if (dif == 1)
    for (int i = 0; i <= l - k; i++) res[i + 1] = arr[k + i];
  else
    for (int i = 0; i <= l - k; i++) res[i + 1] = arr[l - i];
  for (int i = 1; i <= n; i++) cout << res[i] << " ";
}
