#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  int a[200005], ti, ri;
  int t[200005], r[200005], second;
  int b[200005], bl, br;
  scanf("%d%d", &n, &m), second = 0;
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &ti, &ri);
    while (second > 0 && ri >= r[second - 1]) --second;
    t[second] = ti, r[second] = ri, ++second;
  }
  bl = 0, br = r[0], r[second] = 0, ++second;
  for (int i = 0; i < br; ++i) b[i] = a[i];
  std::sort(b, b + br);
  for (int i = 1; i < second; ++i)
    for (int j = r[i - 1]; j > r[i]; --j)
      a[j - 1] = (t[i - 1] == 1) ? b[--br] : b[bl++];
  for (int i = 0; i < n; ++i) printf("%d ", a[i]);
  return 0;
}
