#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int ans[N];
int val[N];
int b[N], len[N];
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) scanf("%d", &val[i]), ans[i] = val[i];
  for (int i = 0; i < m; i++) scanf("%d%d", &b[i], &len[i]);
  int cnt = 0;
  for (int i = 1; i < m; i++) {
    while (~cnt && len[i] > len[cnt]) {
      cnt--;
    }
    cnt++;
    len[cnt] = len[i];
    b[cnt] = b[i];
  }
  sort(val, val + len[0]);
  len[++cnt] = 0;
  int l = 0, r = len[0] - 1;
  for (int i = 0; i < cnt; i++) {
    for (int j = len[i] - 1; j >= len[i + 1]; j--) {
      ans[j] = b[i] == 1 ? val[r--] : val[l++];
    }
  }
  for (int i = 0; i < n; i++) printf("%d%c", ans[i], " \n"[i == n - 1]);
  return 0;
}
