#include <bits/stdc++.h>
using namespace std;
struct data {
  int i, t, r;
};
bool dcmp(data a, data b) { return a.r > b.r; }
bool cmp(int a, int b) { return a < b; }
bool cmp2(int a, int b) { return a > b; }
int main() {
  int n, m;
  cin >> n >> m;
  int arr[n];
  for (int i = 0; i < n; i++) cin >> arr[i];
  data mas[m];
  for (int i = 0; i < m; i++) {
    cin >> mas[i].t >> mas[i].r;
    mas[i].i = i;
  }
  sort(mas, mas + m, dcmp);
  stack<pair<int, int> > stek;
  pair<int, int> para, p1, p2;
  para.first = mas[0].r;
  para.second = n - 1;
  if (mas[0].r < n) stek.push(para);
  if (mas[0].t == 1)
    sort(arr, arr + mas[0].r, cmp);
  else
    sort(arr, arr + mas[0].r, cmp2);
  para.first = 0;
  para.second = mas[0].r - 1;
  stek.push(para);
  int lasti = mas[0].i, lastt = mas[0].t;
  for (int i = 1; i < m; i++) {
    if (mas[i].i < lasti)
      continue;
    else
      lasti = mas[i].i;
    if (mas[i].t == lastt)
      continue;
    else
      lastt = mas[i].t;
    para = stek.top();
    stek.pop();
    if (abs(para.first - para.second) + 1 == mas[i].r) {
      int tmp;
      tmp = para.first;
      para.first = para.second;
      para.second = tmp;
      stek.push(para);
    } else {
      if (para.first < para.second) {
        p2.first = para.first + mas[i].r;
        p2.second = para.second;
        p1.first = p2.first - 1;
        p1.second = para.first;
      } else {
        p1.first = para.first - mas[i].r + 1;
        p1.second = para.first;
        p2.first = p1.first - 1;
        p2.second = para.second;
      }
      stek.push(p2);
      stek.push(p1);
    }
  }
  while (!stek.empty()) {
    para = stek.top();
    stek.pop();
    if (para.first < para.second)
      for (int i = para.first; i <= para.second; i++) cout << arr[i] << " ";
    else
      for (int i = para.first; i >= para.second; i--) cout << arr[i] << " ";
  }
  return 0;
}
