#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  unsigned int n, m;
  cin >> n >> m;
  vector<long> input(n, 0L);
  for (unsigned int i = 0; i < n; ++i) {
    cin >> input[i];
  }
  stack<pair<unsigned int, unsigned int> > s;
  for (unsigned int i = 0; i < m; ++i) {
    unsigned int t, r;
    cin >> t >> r;
    while (!s.empty() && s.top().second < r) {
      s.pop();
    }
    s.push(make_pair(t, r));
  }
  vector<unsigned int> order, range;
  unsigned int r_max = 0;
  while (!s.empty()) {
    order.push_back(s.top().first);
    range.push_back(s.top().second);
    r_max = s.top().second;
    s.pop();
  }
  vector<int> sorted(input.begin(), input.begin() + r_max);
  sort(sorted.begin(), sorted.end());
  int start = 0;
  int end = r_max;
  int id = r_max;
  for (int i = range.size() - 1; i > 0; --i) {
    int nb = range[i] - range[i - 1];
    for (int j = 0; j < nb; j++) {
      if (order[i] == 1) {
        end--;
        id--;
        input[id] = sorted[end];
      } else {
        id--;
        input[id] = sorted[start];
        start++;
      }
    }
  }
  for (int i = id; i > 0; i--) {
    if (order[0] == 1) {
      end--;
      input[i - 1] = sorted[end];
    } else {
      input[i - 1] = sorted[start];
      start++;
    }
  }
  for (unsigned int i = 0; i < n; ++i) {
    cout << input[i] << " ";
  }
  cout << endl;
}
