#include <bits/stdc++.h>
using namespace std;
int a[200010], b[200010], check[200010], namira[200010], vanish[200010];
pair<int, int> nami[200010];
int main() {
  int n, i, m, x, y, M, j, p, k, d1, d, R, L, x1;
  scanf("%d%d", &n, &M);
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  for (i = 0; i < M; i++) {
    scanf("%d%d", &x, &y);
    check[i] = x;
    namira[i] = y;
  }
  k = 0;
  for (i = M - 1; i >= 0; i--) {
    if (vanish[namira[i]] == 0) {
      vanish[namira[i]] = 1;
      nami[k].first = namira[i];
      nami[k].second = i;
      k++;
    }
  }
  sort(nami, nami + k);
  sort(a, a + nami[k - 1].first);
  x = nami[k - 1].first - 1;
  for (i = 0; i <= x; i++) {
    b[i] = a[i];
  }
  p = nami[k - 1].second;
  L = 0;
  R = nami[k - 1].first - 1;
  for (i = k - 2; i >= 0; i--) {
    if (nami[i].second > p) {
      x1 = nami[i].first - 1;
      if (check[p] == 2) {
        d = x - x1;
        d1 = x;
        for (j = L; j < L + d; j++) {
          a[d1] = b[j];
          d1--;
        }
        L = j;
      } else {
        d = x - x1;
        d1 = x;
        for (j = R; j > R - d; j--) {
          a[d1] = b[j];
          d1--;
        }
        R = j;
      }
      x = nami[i].first - 1;
      p = nami[i].second;
    }
  }
  if (check[p] == 2) {
    for (j = 0; j <= x; j++) {
      a[j] = b[R];
      R--;
    }
  } else {
    for (j = 0; j <= x; j++) {
      a[j] = b[L];
      L++;
    }
  }
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  return 0;
}
