#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > chu1;
int a[200005], b[200005], c[100005];
void imp() {
  int k;
  for (k = 0; k <= 10000; k++) c[k] = k;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> a[i];
  imp();
  for (int i = 0; i < m; ++i) {
    int type, r;
    cin >> type >> r;
    r--;
    while (!chu1.empty() && chu1.back().second <= r) chu1.pop_back();
    if (!chu1.empty() && chu1.back().first == type) continue;
    chu1.push_back(make_pair(type, r));
  }
  imp();
  chu1.push_back(pair<int, int>(1, -1));
  int l = 0, r = chu1[0].second, fuckingretard = r;
  sort(a, a + r + 1);
  for (int i = r + 1; i < n; ++i) b[i] = a[i];
  imp();
  for (int i = 1; i < chu1.size(); ++i) {
    int remove = chu1[i - 1].second - chu1[i].second;
    if (chu1[i - 1].first == 1)
      while (remove--) b[fuckingretard--] = a[r--];
    else
      while (remove--) b[fuckingretard--] = a[l++];
  }
  imp();
  for (int i = 0; i < n; ++i) cout << b[i] << ' ';
}
