#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const int N = 200005;
multiset<int> mp[2];
int A[N], ans[N], B[N], ord[N], mx[N], mxind[N];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> A[i];
    mp[0].insert(A[i]);
    mp[1].insert(-A[i]);
  }
  for (int i = 0; i < m; i++) cin >> ord[i] >> B[i];
  mx[m - 1] = B[m - 1];
  mxind[m] = m;
  mxind[m - 1] = m - 1;
  for (int i = m - 2; i >= 0; i--)
    if (B[i] > mx[i + 1]) {
      mx[i] = B[i];
      mxind[i] = i;
    } else {
      mx[i] = mx[i + 1];
      mxind[i] = mxind[i + 1];
    }
  int tp = mxind[0];
  for (int i = n; i > B[tp]; i--) {
    ans[i] = A[i];
    mp[0].erase(mp[0].find(A[i]));
    mp[1].erase(mp[1].find(-A[i]));
  }
  while (1) {
    tp = mxind[tp];
    int val = B[mxind[tp]];
    int nxind = mxind[mxind[tp] + 1];
    for (int i = val; i >= B[nxind] + 1; i--) {
      if (ord[mxind[tp]] == 2) {
        ans[i] = *mp[0].begin();
        mp[0].erase(mp[0].begin());
        mp[1].erase(mp[1].find(-ans[i]));
      } else {
        ans[i] = -(*mp[1].begin());
        mp[1].erase(mp[1].begin());
        mp[0].erase(mp[0].find(ans[i]));
      }
    }
    tp = nxind;
    if (tp == 0) break;
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << " ";
  cout << "\n";
  return 0;
}
