#include <bits/stdc++.h>
using namespace std;
const int MAX = 3e5;
int A[MAX], B[MAX], n, m;
vector<pair<int, int> > ord;
int OUT[MAX];
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < (n); i++) {
    scanf("%d", A + i);
    B[i] = A[i];
  }
  for (int i = 0; i < (m); i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    while (!ord.empty() && ord.back().second <= b) ord.pop_back();
    ord.push_back(make_pair(a, b));
  }
  int k1 = n - 1, k2 = n - 1, k3 = 0;
  if (!ord.empty()) {
    for (; k2 > ord[0].second - 1;) {
      OUT[k1--] = A[k2--];
    }
    sort(B, B + ord[0].second);
  }
  ord.push_back(make_pair(0, 0));
  for (int i = 0; i < ord.size() - 1; i++) {
    if (ord[i].first == 1) {
      while (ord[i].second > ord[i + 1].second) {
        OUT[k1--] = B[k2--];
        ord[i].second--;
      }
    } else {
      while (ord[i].second > ord[i + 1].second) {
        OUT[k1--] = B[k3++];
        ord[i].second--;
      }
    }
  }
  for (int i = 0; i < (n); i++)
    printf("%d%s", OUT[i], (i == n - 1) ? "\n" : " ");
  return 0;
}
