#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 2;
const int INF = 1e9 + 1;
const double EPS = 1e-9;
int n, m;
int a[MAXN];
int r[MAXN], t[MAXN];
int b[MAXN];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  int it = 0;
  for (int i = 0; i < m; ++i) {
    int ct, crt;
    cin >> ct >> crt;
    while (it > 0 && crt >= r[it - 1]) --it;
    t[it] = ct;
    r[it++] = crt;
  }
  r[it] = 0;
  int bl = 0, br = r[0];
  for (int i = 0; i < br; ++i) {
    b[i] = a[i];
  }
  sort(b, b + br);
  for (int i = 1; i < it + 1; ++i) {
    for (int j = r[i - 1]; j > r[i]; --j) {
      if (t[i - 1] == 1) {
        a[j - 1] = b[--br];
      } else
        a[j - 1] = b[bl++];
    }
  }
  for (int i = 0; i < n; ++i) {
    cout << a[i] << " ";
  }
  return 0;
}
