#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int n, m, t, r, a[200005], mx[200005];
deque<int> ans;
multiset<int> ms;
vector<pair<int, int> > v;
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) {
    cin >> t >> r;
    v.push_back({t, r});
  }
  for (int i = m - 1; i > -1; i--) mx[i] = max(v[i].second, mx[i + 1]);
  int f = 0;
  int cur = 0;
  for (int i = 0; i < m; i++) {
    if (mx[i + 1] >= v[i].second) continue;
    t = v[i].first;
    r = v[i].second;
    if (!f) {
      f = 1;
      cur = t;
      for (int j = 0; j < r; j++) ms.insert(a[j]);
      for (int j = r; j < n; j++) ans.push_back(a[j]);
    } else {
      if (t == cur)
        continue;
      else {
        if (cur == 1) {
          while (ms.size() > r)
            ans.push_front(*ms.rbegin()), ms.erase(ms.find(ans.front()));
        } else {
          while (ms.size() > r)
            ans.push_front(*ms.begin()), ms.erase(ms.find(ans.front()));
        }
        if (cur == 1)
          cur = 2;
        else
          cur = 1;
      }
    }
  }
  if (cur == 1) {
    while (ms.size())
      ans.push_front(*ms.rbegin()), ms.erase(ms.find(ans.front()));
  } else {
    while (ms.size())
      ans.push_front(*ms.begin()), ms.erase(ms.find(ans.front()));
  }
  for (auto i : ans) cout << i << ' ';
  return 0;
}
