#include <bits/stdc++.h>
using namespace std;
const int maxn = 2 * 1E5 + 10;
int res[maxn], a[maxn], op[maxn], id[maxn];
int main() {
  int n, m, b, c;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i + 1);
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &b, &c);
    op[c] = b;
    id[c] = i;
  }
  int pos = 0;
  for (int i = n; i > 0; --i) {
    if (op[i]) {
      pos = i;
      break;
    } else
      res[i] = a[i];
  }
  sort(a + 1, a + 1 + pos);
  int l = 1, r = pos, cur = id[pos] - 1, flg;
  while (l <= r) {
    if (op[pos] == 1 && id[pos] > cur) {
      cur = id[pos];
      flg = 0;
    } else if (op[pos] == 2 && id[pos] > cur) {
      cur = id[pos];
      flg = 1;
    }
    if (flg) {
      res[pos] = a[l];
      ++l;
      --pos;
    } else {
      res[pos] = a[r];
      r--;
      pos--;
    }
  }
  for (int i = 1; i <= n; ++i) {
    printf("%d ", res[i]);
  }
  return 0;
}
