#include <bits/stdc++.h>
using namespace std;
long long segs[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int n, m, k;
long long a[200005];
vector<pair<int, int> > q;
int res[200005];
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < m; i++) {
    int r, t;
    cin >> r >> t;
    if (q.empty()) {
      q.push_back(make_pair(r, t - 1));
    } else {
      while (!q.empty() && t - 1 >= q.back().second) {
        q.pop_back();
      }
      q.push_back(make_pair(r, t - 1));
    }
  }
  q.push_back(make_pair(1, 0));
  int l = 0, r = n - 1, ind = n - 1;
  for (int i = 0; i < q.size(); i++) {
    if (i == q.size() - 1) {
      res[ind] = a[l];
      break;
    }
    if (!i) {
      while (r > q[0].second) {
        res[r] = a[r];
        r--;
        ind--;
      }
      sort(a, a + r + 1);
    }
    if (q[i].first == 1) {
      while (ind > q[i + 1].second) {
        res[ind] = a[r];
        ind--;
        r--;
      }
    } else {
      while (ind > q[i + 1].second) {
        res[ind] = a[l];
        ind--;
        l++;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (i) cout << " ";
    cout << res[i];
  }
  cout << endl;
  return 0;
}
