#include <bits/stdc++.h>
const long long mod = 1e9 + 7;
const int MAX = 0x7ffffff;
using namespace std;
struct node {
  int num, op, t;
} temp[200100], q;
int a[200100], b[200100];
int cmp(node c, node d) { return c.t > d.t; }
int main() {
  int i, j, m, n, ans, l, r;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &temp[i].op, &temp[i].t);
    q.t = temp[i].t;
    q.op = temp[i].op;
    temp[i].num = i;
  }
  sort(temp + 1, temp + 1 + m, cmp);
  sort(b + 1, b + temp[1].t + 1);
  ans = 1;
  l = 1;
  r = temp[1].t;
  temp[m + 1].num = m + 1;
  temp[m + 1].t = 0;
  for (i = 2; i <= m + 1; i++) {
    if (temp[ans].num < temp[i].num) {
      for (j = temp[ans].t; j > temp[i].t; j--) {
        if (temp[ans].op == 1)
          a[j] = b[r--];
        else
          a[j] = b[l++];
      }
      ans = i;
    }
  }
  for (i = 1; i <= n; i++) printf("%d ", a[i]);
  return 0;
}
