#include <bits/stdc++.h>
bool compare(int a, int b) { return a > b; }
using namespace std;
int arr[200100], cop[200100];
pair<int, int> p[200100];
vector<pair<int, int> > v;
map<int, int> hah;
int main() {
  int n, m, a, b;
  hah.clear();
  set<int, greater<int> > second;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
  second.clear();
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &a, &b);
    p[i].first = a;
    p[i].second = b;
    hah[b] = i;
    second.insert(b);
  }
  set<int, greater<int> >::iterator it;
  int curr = -1, j;
  for (it = second.begin(); it != second.end(); ++it) {
    if (hah[*it] > curr) {
      v.push_back(p[hah[*it]]);
      curr = hah[*it];
    }
  }
  for (int i = 0; i < n; i++) {
    cop[i] = arr[i];
  }
  sort(cop, cop + v[0].second);
  int bl = 0, br = v[0].second;
  v.push_back(pair<int, int>(0, 0));
  for (int i = 1; i <= v.size(); i++) {
    for (j = v[i - 1].second; j > v[i].second; j--) {
      if (v[i - 1].first == 1) {
        arr[j - 1] = cop[--br];
      } else {
        arr[j - 1] = cop[bl++];
      }
    }
  }
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  return 0;
}
