#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const double eps = 1e-5;
int a[maxn];
int b[maxn], t[maxn], r[maxn];
int main() {
  int n, m;
  int tt, rr;
  while (cin >> n >> m) {
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int s = 0;
    while (m--) {
      scanf("%d%d", &tt, &rr);
      while (s > 0 && rr > r[s - 1]) s--;
      r[s] = rr;
      t[s] = tt;
      s++;
    }
    int bl = 0, br = r[0];
    r[s] = 0;
    s++;
    for (int i = 0; i < r[0]; i++) b[i] = a[i];
    sort(b, b + r[0]);
    for (int i = 1; i < s; i++)
      for (int j = r[i - 1]; j > r[i]; j--)
        a[j - 1] = (t[i - 1] == 1) ? b[--br] : b[bl++];
    cout << a[0];
    for (int i = 1; i < n; i++) cout << ' ' << a[i];
    cout << endl;
  }
  return 0;
}
