#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int Seed = 233333;
int n, m;
int a[maxn];
inline int Rand() { return Seed = (Seed * 122777ll + 19260817) % 998244353; }
namespace IO {
const int S = 1 << 20;
char buf[S], *p = buf + S;
inline char IN() {
  if (p == buf + S) fread(buf, 1, S, stdin), p = buf;
  return *(p++);
}
}  // namespace IO
inline void R_Int(int &a) {
  register char ch;
  bool flag;
  while (ch = getchar(), (ch < '0' || ch > '9') && (ch != '-'))
    ;
  flag = (ch == '-');
  a = flag ? 0 : (ch - '0');
  while (ch = getchar(), ch >= '0' && ch <= '9')
    a = (a << 1) + (a << 3) + ch - '0';
  a = flag ? (-a) : a;
};
struct Node {
  Node *lch, *rch;
  int val, size;
  bool Add;
  inline void MainTain() { this->size = lch->size + rch->size + 1; }
} node[maxn];
int tot;
typedef pair<Node *, Node *> P;
Node *Root, *Null;
inline void Init() {
  Null = &node[++tot];
  Null->size = 0;
  Null->lch = Null->rch = Null;
}
inline void Push(Node *u) {
  u->Add ^= 1;
  swap(u->lch, u->rch);
}
inline void Pushdown(Node *u) {
  u->Add = 0;
  if (u->lch != Null) Push(u->lch);
  if (u->rch != Null) Push(u->rch);
}
void Build(Node *&u, int le, int ri) {
  if (le > ri) return;
  u = &node[++tot];
  int mid = (le + ri) >> 1;
  u->val = a[mid];
  u->lch = u->rch = Null;
  if (le == ri) return u->MainTain(), void();
  Build(u->lch, le, mid - 1);
  Build(u->rch, mid + 1, ri);
  u->MainTain();
}
void Pr(Node *u) {
  if (u->Add) Pushdown(u);
  if (u->lch != Null) Pr(u->lch);
  printf("%d ", u->val);
  if (u->rch != Null) Pr(u->rch);
}
P Split(Node *u, int K) {
  if (u == Null) return P(Null, Null);
  if (u->Add) Pushdown(u);
  P tmp;
  int LeftSize = u->lch->size;
  if (K <= LeftSize) {
    tmp = Split(u->lch, K);
    u->lch = tmp.second;
    u->MainTain();
    tmp.second = u;
  } else {
    tmp = Split(u->rch, K - LeftSize - 1);
    u->rch = tmp.first;
    u->MainTain();
    tmp.first = u;
  }
  return tmp;
}
Node *Merge(Node *A, Node *B) {
  if (A == Null) return B;
  if (B == Null) return A;
  if (A->Add) Pushdown(A);
  if (B->Add) Pushdown(B);
  if (Rand() % (A->size + B->size) < A->size) {
    A->rch = Merge(A->rch, B);
    A->MainTain();
    return A;
  } else {
    B->lch = Merge(A, B->lch);
    B->MainTain();
    return B;
  }
}
inline void Reverse(int r) {
  P tmp = Split(Root, r);
  Node *u = tmp.first;
  u->Add ^= 1;
  swap(u->lch, u->rch);
  Root = Merge(tmp.first, tmp.second);
}
bool Down(const int &a, const int &b) { return a > b; }
bool Up(const int &a, const int &b) { return a < b; }
struct Dir {
  int r, tp;
  Dir() {}
  Dir(int a, int b) { tp = a, r = b; }
} q[maxn];
int h, t;
int main() {
  Init();
  R_Int(n), R_Int(m);
  for (register int i = 1; i <= n; i++) R_Int(a[i]);
  int tp, r;
  h = 1, t = 0;
  for (register int i = 1; i <= m; i++) {
    R_Int(tp), R_Int(r);
    while (h <= t && q[t].r <= r) t--;
    if (tp != q[t].tp) q[++t] = Dir(tp, r);
  }
  if (q[h].tp == 1)
    sort(a + 1, a + 1 + q[h].r, Up);
  else
    sort(a + 1, a + 1 + q[h].r, Down);
  Build(Root, 1, n);
  h++;
  while (h <= t) {
    Reverse(q[h++].r);
  }
  Pr(Root);
  puts("");
  return 0;
}
