#include <bits/stdc++.h>
using namespace std;
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const int MAXN = 2e5 + 5;
const long long MOD = 1e9 + 7;
int num[MAXN], t[MAXN], v[MAXN], ans[MAXN];
map<int, int> vv;
void solve() {
  int n, m, i, tt, a, mxnum, tmp;
  scanf("%d%d", &n, &m);
  for ((i) = (int)(0); (i) < (int)(n); (i)++) {
    scanf("%d", &v[i]);
    vv[v[i]]++;
  }
  for ((i) = (int)(0); (i) < (int)(m); (i)++) {
    scanf("%d%d", &tt, &a);
    t[a - 1] = tt;
    num[a - 1] = i + 1;
  }
  tt = 0;
  mxnum = 0;
  for (i = n - 1; i >= 0; i--) {
    if (num[i] > mxnum) {
      mxnum = num[i];
      tt = t[i];
    }
    if (tt == 0) {
      tmp = v[i];
    } else if (tt == 1) {
      tmp = vv.rbegin()->first;
    } else {
      tmp = vv.begin()->first;
    }
    ans[i] = tmp;
    vv[tmp]--;
    if (vv[tmp] == 0) {
      vv.erase(tmp);
    }
  }
  for ((i) = (int)(0); (i) < (int)(n); (i)++) {
    printf("%d ", ans[i]);
  }
  putchar('\n');
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
}
