#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e6 + 123;
multiset<int> st;
vector<int> ans;
pair<int, int> mx(pair<int, int> a, pair<int, int> b) {
  if (a.first >= b.first)
    return a;
  else
    return b;
}
bool cmp(int a, int b) {
  if (a > b) return 1;
  return 0;
}
int n, m, a[N], cnt;
pair<int, int> q[N], t[N], res[N];
void build(int v = 1, int tl = 1, int tr = m) {
  if (tl == tr) {
    t[v] = make_pair(q[tl].second, tl);
    return;
  }
  int mid = (tl + tr) / 2;
  build(v * 2, tl, mid);
  build(v * 2 + 1, mid + 1, tr);
  t[v] = mx(t[v * 2], t[v * 2 + 1]);
}
pair<int, int> get_max(int l, int r, int v = 1, int tl = 1, int tr = m) {
  if (tl > tr || l > r || tl > r || l > tr) return make_pair(0, 0);
  if (l <= tl && tr <= r) return t[v];
  int mid = (tl + tr) / 2;
  return mx(get_max(l, r, v * 2, tl, mid),
            get_max(l, r, v * 2 + 1, mid + 1, tr));
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1, x, y; i <= m; i++) {
    scanf("%d%d", &x, &y);
    q[i] = make_pair(x, y);
  }
  build();
  pair<int, int> it = get_max(1, m);
  while (it.second <= m) {
    if (cnt == 0)
      res[++cnt] = (make_pair(it.first, q[it.second].first));
    else if (res[cnt].first == it.first) {
      if (res[cnt - 1].second == q[it.second].first)
        cnt--;
      else
        res[cnt] = make_pair(it.first, q[it.second].first);
    } else if (res[cnt].second != q[it.second].first)
      res[++cnt] = make_pair(it.first, q[it.second].first);
    if (it.second == m) break;
    it = get_max(it.second + 1, m);
  }
  for (int i = n; i > res[1].first; i--) ans.push_back(a[i]);
  for (int i = 1; i <= res[1].first; i++) st.insert(a[i]);
  for (int i = 1; i <= cnt; i++) {
    for (int j = res[i].first; j > res[i + 1].first; j--) {
      if (res[i].second == 1) {
        ans.push_back(*--st.end());
        st.erase(--st.end());
      } else {
        ans.push_back(*st.begin());
        st.erase(st.begin());
      }
    }
  }
  for (int i = (int)(ans.size()) - 1; i >= 0; i--) printf("%d ", ans[i]);
  return 0;
}
