#include <bits/stdc++.h>
using namespace std;
struct operation {
  bool is_asc;
  int ind;
  int step;
};
struct vec_view {
  vec_view(int* b, int* e) : begin_(b), end_(e), is_reversed_(false) {}
  int& operator[](int i) {
    if (!is_reversed_)
      return begin_[i];
    else
      return end_[-i - 1];
  }
  int size() const { return end_ - begin_; }
  void shrink_to(int n) {
    int dx = size() - n;
    if (!is_reversed_)
      end_ -= dx;
    else
      begin_ += dx;
  }
  void reverse() { is_reversed_ = !is_reversed_; }
  bool is_asc() const { return !is_reversed_; }

 private:
  bool is_reversed_;
  int* begin_;
  int* end_;
};
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a;
  copy_n(istream_iterator<int>(cin), n, back_inserter(a));
  vector<operation> ops;
  for (int i = 0; i < m; ++i) {
    int t, r;
    cin >> t >> r;
    ops.push_back({t == 1, r - 1, i});
  }
  sort(ops.begin(), ops.end(), [](operation const& x, operation const& y) {
    if (x.ind > y.ind)
      return true;
    else if (x.ind < y.ind)
      return false;
    if (x.step > y.step)
      return true;
    else if (x.step < y.step)
      return false;
    return false;
  });
  sort(a.begin(), a.begin() + ops[0].ind + 1);
  vector<int> res;
  for (int i = a.size(); i > ops[0].ind + 1; --i) res.push_back(a[i - 1]);
  vec_view view(&a[0], &a[0] + ops[0].ind + 1);
  if (!ops[0].is_asc) view.reverse();
  int step = ops[0].step;
  for (const auto& op : ops) {
    if (op.step <= step) continue;
    for (int i = view.size(); i > op.ind + 1; --i) res.push_back(view[i - 1]);
    view.shrink_to(op.ind + 1);
    if (view.is_asc() != op.is_asc) view.reverse();
    step = op.step;
  }
  for (int i = view.size(); i > 0; --i) res.push_back(view[i - 1]);
  copy(res.rbegin(), res.rend(), ostream_iterator<int>(cout, " "));
}
