#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long MX = 2e5 + 3;
vector<pair<long long, long long>> task;
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, m;
  cin >> n >> m;
  long long a[n], out[n];
  for (long long i = 0; i < n; i++) cin >> a[i];
  for (long long i = 0; i < m; i++) {
    long long t, r;
    cin >> t >> r;
    if (task.size())
      while (task.back().first <= r) {
        task.pop_back();
        if (!task.size()) break;
      }
    task.push_back(make_pair(r, t - 1));
  }
  reverse(task.begin(), task.end());
  long long k = task.back().first, f = 0;
  sort(a, a + k);
  for (long long i = k; i < n; i++) out[i] = a[i];
  while (task.size()) {
    auto temp = task.back();
    task.pop_back();
    pair<long long, long long> last;
    if (task.size())
      last = task.back();
    else
      last = make_pair(0, 1);
    if (temp.second == 1)
      for (long long i = ((temp.first) - 1); i >= last.first; i--)
        out[i] = a[f], f++;
    if (temp.second == 0)
      for (long long i = last.first + f; i < temp.first + f; i++)
        out[i - f] = a[i];
  }
  for (long long i = 0; i < n; i++) cout << out[i] << " ";
  cout << endl;
  return 0;
}
