#include <bits/stdc++.h>
using namespace std;
int a[200001];
int ans[200001];
int ord[200001];
int ad[200001];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i, n, m, o, idx;
  cin >> n >> m;
  for (i = 1; i < n + 1; i++) cin >> a[i];
  for (i = 1; i < m + 1; i++) {
    cin >> o >> idx;
    ord[idx] = i;
    ad[idx] = o;
  }
  i = n;
  while (ad[i] == 0 && i >= 1) i--;
  int tym = ord[i];
  int asc = ad[i];
  sort(a + 1, a + i + 1);
  if (ad[i] == 2) reverse(a + 1, a + i + 1);
  int j;
  for (j = 1; j < n + 1; j++) ans[j] = a[j];
  deque<int> q;
  for (j = 1; j <= i; j++) q.push_back(a[j]);
  int cur = asc;
  for (; i >= 1; i--) {
    if (ord[i] > tym) {
      tym = ord[i];
      cur = ad[i];
      if (ad[i] == asc) {
        int num = q.back();
        ans[i] = num;
        q.pop_back();
      } else {
        int num = q.front();
        ans[i] = num;
        q.pop_front();
      }
    } else {
      if (cur == asc) {
        int num = q.back();
        ans[i] = num;
        q.pop_back();
      } else {
        int num = q.front();
        ans[i] = num;
        q.pop_front();
      }
    }
  }
  for (i = 1; i < n + 1; i++) cout << ans[i] << " ";
  return 0;
}
