#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int n, m, i, j, max = 0;
  cin >> n >> m;
  long long int arr[n];
  for (i = 0; i < n; i++) cin >> arr[i];
  vector<pair<long long int, long long int> > vec;
  stack<long long int> s;
  for (i = 0; i < m; i++) {
    long long int t, r;
    cin >> t >> r;
    vec.push_back(make_pair(t, r));
    if (r > max) max = r;
  }
  for (i = 0; i < m; i++) {
    while (!s.empty() && vec[i].second >= vec[s.top()].second) {
      s.pop();
    }
    s.push(i);
  }
  vector<pair<long long int, long long int> > vec2;
  while (!s.empty()) {
    vec2.push_back(make_pair(vec[s.top()].first, vec[s.top()].second));
    s.pop();
  }
  reverse(vec2.begin(), vec2.end());
  priority_queue<long long int> pq;
  priority_queue<long long int, vector<long long int>, greater<long long int> >
      pq2;
  for (i = 0; i < max; i++) {
    pq.push(arr[i]);
    pq2.push(arr[i]);
  }
  for (i = 0; i < vec2.size() - 1; i++) {
    long long int t = vec2[i].first;
    long long int y = vec2[i].second - vec2[i + 1].second;
    long long int index = vec2[i].second - 1;
    if (t == 1) {
      while (y != 0) {
        arr[index] = pq.top();
        pq.pop();
        y--;
        index--;
      }
    } else {
      while (y != 0) {
        arr[index] = pq2.top();
        pq2.pop();
        y--;
        index--;
      }
    }
  }
  long long int t = vec2[i].first;
  long long int y = vec2[i].second;
  long long int index = vec2[i].second - 1;
  if (t == 1) {
    while (y != 0) {
      arr[index] = pq.top();
      pq.pop();
      y--;
      index--;
    }
  } else {
    while (y != 0) {
      arr[index] = pq2.top();
      pq2.pop();
      y--;
      index--;
    }
  }
  for (i = 0; i < n; i++) cout << arr[i] << " ";
}
