#include <bits/stdc++.h>
using namespace std;
int n, m;
long long int a[200007];
pair<long long int, int> r[200007];
std::vector<pair<long long int, int>> vr;
deque<long long int> dq, res;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) std::cin >> a[i];
  for (int i = 0; i < m; i++) std::cin >> r[i].second >> r[i].first;
  for (int i = m - 2; i >= 0; i--) r[i].first = max(r[i].first, r[i + 1].first);
  for (int i = 0; i < m - 1; i++)
    if (r[i].first != r[i + 1].first) vr.push_back(r[i]);
  vr.push_back(r[m - 1]);
  vr.push_back({0, 1});
  for (int i = vr[0].first + 1; i <= n; i++) res.push_back(a[i]);
  sort(a + 1, a + vr[0].first + 1);
  for (int i = 1; i < vr[0].first + 1; i++) dq.push_back(a[i]);
  for (int i = 0; i < vr.size() - 1; i++) {
    int tofix = vr[i].first - vr[i + 1].first;
    while (tofix--) {
      long long int tp;
      if (vr[i].second == 1)
        tp = dq.back(), dq.pop_back();
      else
        tp = dq.front(), dq.pop_front();
      res.push_front(tp);
    }
  }
  for (auto e : res) printf("%d ", e);
}
