#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmin(T &a, T b) {
  a = min(a, b);
}
template <typename T>
void chkmax(T &a, T b) {
  a = max(a, b);
}
inline int fread(void) {
  int ret = 0, op = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') op = -1;
  for (; isdigit(ch); ch = getchar()) ret = (ret << 1) + (ret << 3) - '0' + ch;
  return ret * op;
}
const int MAXN = 2e5 + 10;
const int MAXM = +10;
int n, m, a[MAXN], c[MAXN];
struct rec {
  int t, r;
  bool operator<(const rec &b) const { return r < b.r; }
} s[MAXN];
int top;
inline void init(void) {
  n = fread(), m = fread();
  for (int i = 1; i <= n; ++i) a[i] = fread(), c[i] = a[i];
}
int lt, rt;
inline void work(void) {
  rec now;
  top = 0;
  for (int i = 1; i <= m; ++i) {
    now.t = fread(), now.r = fread();
    while (top && s[top] < now) --top;
    s[++top] = now;
  }
  sort(c + 1, c + s[1].r + 1);
  lt = 1;
  rt = s[1].r;
  ++top;
  s[top].r = 0;
  for (int i = 2; i <= top; ++i) {
    if (s[i - 1].t == 1) {
      for (int j = s[i - 1].r; j > s[i].r; --j) a[j] = c[rt--];
    } else {
      for (int j = s[i - 1].r; j > s[i].r; --j) a[j] = c[lt++];
    }
  }
  for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
}
int main() {
  init();
  work();
  return 0;
}
