#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b); }
using namespace std;
int t[200005] = {0}, r[200005] = {0}, T, R, top = 0, n, m, a[200005] = {0};
int px[200005] = {0};
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &T, &R);
    while (top && R >= r[top]) top--;
    top++;
    t[top] = T, r[top] = R;
  }
  for (int i = 1; i <= r[1]; i++) px[i] = a[i];
  int ll = 0, rr = r[1] + 1;
  sort(px + 1, px + r[1] + 1);
  r[top + 1] = 0;
  for (int i = 1; i <= top; i++) {
    if (t[i] == 1)
      for (int j = r[i]; j > r[i + 1]; j--) a[j] = px[--rr];
    else
      for (int j = r[i]; j > r[i + 1]; j--) a[j] = px[++ll];
  }
  for (int i = 1; i <= n; i++) printf("%d", a[i]), putchar(i == n ? '\n' : ' ');
  return 0;
}
