#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  int n, m, i;
  cin >> n >> m;
  int a[n + 1];
  for (i = 1; i <= n; i++) cin >> a[i];
  deque<pair<int, int>> dq;
  pair<int, int> x;
  for (i = 1; i <= m; i++) {
    cin >> x.first >> x.second;
    while (!dq.empty() && x.second >= dq.back().second) dq.pop_back();
    dq.push_back(x);
  }
  x = dq.front(), dq.pop_front();
  sort(a + 1, a + (x.second + 1));
  deque<int> b;
  for (i = 1; i <= x.second; i++) b.push_back(a[i]);
  pair<int, int> prevX;
  while (!dq.empty()) {
    prevX = x;
    x = dq.front(), dq.pop_front();
    for (i = prevX.second; i > x.second; i--)
      if (prevX.first == 1)
        a[i] = b.back(), b.pop_back();
      else
        a[i] = b.front(), b.pop_front();
  }
  while (!b.empty()) {
    if (x.first == 1)
      a[x.second--] = b.back(), b.pop_back();
    else
      a[x.second--] = b.front(), b.pop_front();
  }
  for (i = 1; i <= n; i++) cout << a[i] << ' ';
  return 0;
}
