#include <bits/stdc++.h>
long long r[200005];
long long t[200005];
long long bj[200005];
int main() {
  long long n, i, x;
  long long ar[200005];
  scanf("%lld%lld", &n, &x);
  for (i = 0; i < n; i++) scanf("%lld", &ar[i]);
  long long a, b;
  long long k = 0;
  while (x--) {
    scanf("%lld%lld", &a, &b);
    while (k > 0 && b >= r[k - 1]) k--;
    r[k] = b;
    t[k] = a;
    k++;
  }
  long long m = r[0];
  long long k1 = 0;
  for (i = 0; i < m; i++) bj[i] = ar[i];
  long long j;
  r[k] = 0;
  k++;
  std::sort(bj, bj + m);
  for (i = 1; i < k; i++) {
    for (j = r[i - 1]; j > r[i]; j--) {
      if (t[i - 1] == 1)
        ar[j - 1] = bj[--m];
      else
        ar[j - 1] = bj[k1++];
    }
  }
  for (i = 0; i < n; i++) printf("%lld ", ar[i]);
  return 0;
}
