#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[1000010];
int main() {
  cin >> n >> m;
  vector<int> ans(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    ans[i] = arr[i];
  }
  vector<int> order(m);
  vector<int> firstr(m);
  vector<pair<int, int> > posr(m);
  for (int i = 0; i < m; i++) {
    cin >> order[i] >> firstr[i];
    posr[i].first = firstr[i];
    posr[i].second = i;
  }
  sort(posr.rbegin(), posr.rend());
  int lastHeight = posr[0].first;
  int lastpos = posr[0].second;
  int l = 0, r = lastHeight - 1;
  sort(arr, arr + lastHeight);
  for (int i = 1; i < m; i++) {
    if (posr[i].second > lastpos) {
      int id = posr[i].second;
      if (order[lastpos] == 1) {
        int temp = lastHeight - 1;
        while (temp >= firstr[id]) {
          ans[temp] = arr[r];
          r--;
          temp--;
        }
      } else {
        int temp = lastHeight - 1;
        while (temp >= firstr[id]) {
          ans[temp] = arr[l];
          l++;
          temp--;
        }
      }
      lastHeight = posr[i].first;
      lastpos = posr[i].second;
    }
  }
  if (order[lastpos] == 1) {
    int temp = lastHeight - 1;
    while (temp >= 0) {
      ans[temp] = arr[r];
      r--;
      temp--;
    }
  } else {
    int temp = lastHeight - 1;
    while (temp >= 0) {
      ans[temp] = arr[l];
      l++;
      temp--;
    }
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
}
