#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  vector<long long> v(n);
  vector<pair<int, int> > order(m);
  int num, r;
  for (int i = 0; i < n; ++i) cin >> v[i];
  for (int i = 0; i < m; ++i) {
    cin >> num >> r;
    order[i] = make_pair(num, r);
  }
  vector<pair<int, int> > query;
  int nprevious = 0, rprevious = 0;
  for (int i = m - 1; i >= 0; --i) {
    pair<int, int> p = order[i];
    int num = p.first, r = p.second;
    if (r < rprevious) continue;
    if (num == nprevious) query.pop_back();
    query.push_back(make_pair(num, r));
    nprevious = num;
    rprevious = r;
  }
  vector<long long> vreport(n);
  int size = query.size();
  int index = n - 1;
  pair<int, int> p = query[size - 1];
  nprevious = p.first;
  rprevious = p.second;
  for (int k = 0; k < n - rprevious; ++k) vreport[index] = v[index], --index;
  int left = 0, right = rprevious;
  v.erase(v.begin() + rprevious, v.end());
  sort(v.begin(), v.end());
  for (int i = size - 2; i >= 0; --i) {
    pair<int, int> p = query[i];
    int num = p.first;
    int r = p.second;
    int dis = rprevious - r;
    if (nprevious == 1) {
      for (int k = 0; k < dis; ++k) vreport[index--] = v[right - k - 1];
      right -= dis;
    } else {
      for (int k = 0; k < dis; ++k) vreport[index--] = v[left + k];
      left += dis;
    }
    nprevious = num;
    rprevious = r;
  }
  if (nprevious == 1)
    for (int k = 0; k < rprevious; ++k) vreport[index--] = v[right - k - 1];
  else
    for (int k = 0; k < rprevious; ++k) vreport[index--] = v[left + k];
  for (int i = 0; i < n - 1; ++i) cout << vreport[i] << " ";
  cout << vreport[n - 1] << "\n";
  return 0;
}
