#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n, m;
int arrays[MAXN + 10], brrays[MAXN + 10];
int op[MAXN + 10], range[MAXN + 10];
int p;
int main(void) {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &arrays[i]);
  for (int i = 1; i <= m; i++) {
    int tempa, tempb;
    scanf("%d%d", &tempa, &tempb);
    while (p && tempb >= range[p]) p--;
    p++;
    range[p] = tempb;
    op[p] = tempa;
  }
  for (int i = 1; i <= n; i++) brrays[i] = arrays[i];
  sort(arrays + 1, arrays + 1 + range[1]);
  int l = 1, r = range[1], t = 0, f;
  for (int i = range[1]; i >= 1; i--) {
    if (t < p && range[t + 1] == i) f = op[++t];
    if (f == 2)
      brrays[i] = arrays[l++];
    else
      brrays[i] = arrays[r--];
  }
  for (int i = 1; i <= n; i++) printf("%d ", brrays[i]);
  printf("\n");
  return 0;
}
