#include <bits/stdc++.h>
using namespace std;
pair<int, int> query[200005];
vector<int> v;
int ans[200005];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    v.push_back(a);
  }
  int last = 0, lastt;
  cin >> query[0].first >> query[0].second;
  for (int i = 1; i < m; i++) {
    int a, b;
    cin >> a >> b;
    int lo = 0, hi = last;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (query[mid].second <= b)
        hi = mid - 1;
      else
        lo = mid + 1;
    }
    query[lo] = pair<int, int>(a, b);
    last = lo;
  }
  lastt = last;
  vector<int> vv(v.begin(), v.begin() + query[0].second);
  sort(vv.begin(), vv.end());
  deque<int> Q(vv.begin(), vv.end());
  for (int i = query[0].second; i < n; i++) ans[i] = v[i];
  int idx = 0;
  last = query[0].first;
  for (int i = query[0].second - 1; i >= 0; i--) {
    if (i == query[idx].second - 1 && idx <= lastt) {
      last = query[idx].first;
      idx++;
    }
    if (last == 1) {
      ans[i] = Q.back();
      Q.pop_back();
    } else {
      ans[i] = Q.front();
      Q.pop_front();
    }
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
  return 0;
}
