#include <bits/stdc++.h>
using namespace std;
const int maxn = 2E5 + 77;
void putint(int x) {
  static bool first = true;
  if (first) {
    printf("%d", x);
    first = false;
  } else
    printf(" %d", x);
}
struct QUERY {
  int t, r;
} Q[maxn];
int cnt = 0;
int N, M, A[maxn], B[maxn], pb = 0;
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < N; ++i) scanf("%d", A + i);
  for (int i = 0; i < M; ++i) {
    int t, r;
    scanf("%d%d", &t, &r);
    while (cnt && r >= Q[cnt - 1].r) --cnt;
    if (!cnt || t != Q[cnt - 1].t) Q[cnt++] = (QUERY){t, r};
  }
  Q[cnt] = (QUERY){0, 0};
  sort(A, A + Q[0].r);
  int ptr[2] = {0, Q[0].r - 1}, d = Q[0].t == 1;
  for (int i = 0; i < cnt; ++i) {
    for (int j = Q[i].r; j > Q[i + 1].r; --j) {
      B[pb++] = A[ptr[d]];
      ptr[d] += d ? -1 : 1;
    }
    d ^= 1;
  }
  for (int i = Q[0].r - 1; i >= 0; --i) putint(B[i]);
  for (int i = Q[0].r; i < N; ++i) putint(A[i]);
  printf("\n");
}
