#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
int A[N], B[N];
int ret[N];
int a[N], b[N];
const int inf = MOD;
int main() {
  ios_base::sync_with_stdio(false);
  int n, t, m, l, k, ans, i, j, res = 0, fl;
  t = 1;
  while (t--) {
    int x;
    cin >> n >> m;
    int type, maxi = 0;
    for (i = 0; i < n; i++) {
      cin >> a[i];
      b[i] = a[i];
    }
    for (i = 0; i < n + 5; i++) {
      A[i] = -inf;
      B[i] = inf;
    }
    for (i = 0; i < m; i++) {
      cin >> type;
      cin >> x;
      A[x - 1] = i;
      B[x - 1] = type;
    }
    int r = n - 1;
    l = 0;
    for (i = n - 1; i >= 0; --i) {
      if (A[i + 1] > A[i]) {
        A[i] = A[i + 1];
        B[i] = B[i + 1];
      }
      if (A[i] == -inf)
        ret[i] = a[r--];
      else {
        if (A[i + 1] == -inf) {
          sort(b, b + i + 1);
          r = i;
          l = 0;
        }
        if (B[i] == 1)
          ret[i] = b[r--];
        else
          ret[i] = b[l++];
      }
    }
    for (i = 0; i < n; i++) cout << ret[i] << ' ';
    cout << '\n';
  }
  return 0;
}
