#include <bits/stdc++.h>
using namespace std;
int a[200005], tim[200005], val[200005];
int main() {
  int n, m, i, j, x, y, v, max1;
  scanf("%d%d", &n, &m);
  multiset<int> s1, s2;
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    s1.insert(a[i]);
    s2.insert(-a[i]);
  }
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    tim[y - 1] = i;
    val[y - 1] = x;
  }
  vector<int> ans;
  v = 0;
  max1 = -1;
  for (i = n - 1; i >= 0; i--) {
    if (val[i] && tim[i] > max1) {
      v = val[i];
      max1 = tim[i];
    }
    if (v == 0) {
      ans.push_back(a[i]);
      s1.erase(s1.find(a[i]));
      s2.erase(s2.find(-a[i]));
    }
    if (v == 1) {
      int v1 = *s2.begin();
      ans.push_back(-v1);
      s1.erase(s1.find(-v1));
      s2.erase(s2.find(v1));
    }
    if (v == 2) {
      int v1 = *s1.begin();
      ans.push_back(v1);
      s1.erase(s1.find(v1));
      s2.erase(s2.find(-v1));
    }
  }
  for (i = n - 1; i >= 0; i--) {
    printf("%d ", ans[i]);
  }
  printf("\n");
  return 0;
}
