#include <bits/stdc++.h>
using namespace std;
long long ans[200005], a[200005], t[200005], b[200005];
int main() {
  long long n, m, temp, x, y, p, q;
  long long s = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> ans[i];
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    while (s > 0 && a[s - 1] <= y) {
      s--;
    }
    t[s] = x, a[s] = y, s++;
  }
  a[s] = 0;
  for (int i = 0; i < a[0]; i++) b[i] = ans[i];
  sort(b, b + a[0]);
  temp = a[0];
  int start = 0;
  for (int i = 1; i <= s; i++) {
    for (int j = a[i - 1]; j > a[i]; j--) {
      if (t[i - 1] == 1) {
        ans[j - 1] = b[--temp];
      } else {
        ans[j - 1] = b[start++];
      }
    }
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
}
