#include <bits/stdc++.h>
using namespace std;
struct node {
  int t;
  int p;
};
stack<int> ans;
node order[200010];
node stk[200010];
int num[200010];
int n, m, top, pos;
int cmp1(int u, int v) { return u < v; }
int cmp2(int u, int v) { return u > v; }
void init() {
  int i, j, maxx;
  stk[0].t = 0, stk[0].p = 0;
  maxx = 0, top = 0;
  for (i = m; i >= 1; i--) {
    if (order[i].t == stk[top].t) {
      if (order[i].p > stk[top].p) {
        stk[top] = order[i];
      }
    } else {
      if (order[i].p > stk[top].p) {
        top++;
        stk[top] = order[i];
      }
    }
  }
  return;
}
void calculate() {
  int i, t, l, r;
  while (!ans.empty()) ans.pop();
  l = 1, r = n;
  while (r > stk[top].p) {
    ans.push(num[r]);
    r--;
  }
  if (stk[top].t == 1)
    sort(num + l, num + r + 1, cmp1);
  else
    sort(num + l, num + r + 1, cmp2);
  top--;
  while (top >= 1) {
    if (l <= r) {
      while (r > l + stk[top].p - 1) {
        ans.push(num[r]);
        r--;
      }
      t = l, l = r, r = t;
    } else {
      while (r < l - stk[top].p + 1) {
        ans.push(num[r]);
        r++;
      }
      t = l, l = r, r = t;
    }
    top--;
  }
  if (l <= r) {
    while (l <= r) {
      ans.push(num[r]);
      r--;
    }
  } else {
    while (r <= l) {
      ans.push(num[r]);
      r++;
    }
  }
  while (!ans.empty()) {
    printf("%d ", ans.top());
    ans.pop();
  }
  printf("\n");
  return;
}
int main() {
  int i, j, maxx, l, r;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (i = 1; i <= n; i++) {
      scanf("%d", &num[i]);
    }
    for (i = 1; i <= m; i++) {
      scanf("%d%d", &order[i].t, &order[i].p);
    }
    init();
    calculate();
  }
  return 0;
}
