#include <bits/stdc++.h>
using namespace std;
const int INF = (int)(INT_MAX - 100);
const int N = (int)(2e+5);
const long long mod = (int)(1e+9 + 7);
int v[N + 1];
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = (1); i <= (n); i++) scanf("%d", &v[i]);
  vector<pair<int, int> > q(n + 1, {0, 0});
  int M = 0, t, rr;
  for (int i = (1); i <= (m); i++) {
    scanf("%d%d", &t, &rr);
    q[rr] = {i, t};
    M = max(M, rr);
  }
  sort(v + 1, v + M + 1);
  int l = 1, r = n, p = 0;
  t = 1;
  vector<int> ans(n);
  for (int i = (n); i >= (1); i--) {
    if (p < q[i].first) t = q[i].second;
    if (p < q[i].first) p = q[i].first;
    if (t == 1)
      ans[i - 1] = v[r];
    else
      ans[i - 1] = v[l];
    if (t == 1)
      r--;
    else
      l++;
  }
  for (auto x : ans) cout << x << " ";
  return 0;
}
