#include <bits/stdc++.h>
using namespace std;
int arr[200000 + 1];
int main() {
  long long int n, k;
  cin >> n >> k;
  vector<long long int> r;
  vector<long long int> ans;
  vector<pair<long long int, long long int> > c;
  for (long long int i = 0; i < n; i++) {
    long long int tmp;
    cin >> tmp;
    r.push_back(tmp);
  }
  for (long long int i = 1; i <= k; i++) {
    long long int t, r1;
    cin >> t >> r1;
    r1--;
    arr[i] = t;
    c.push_back(make_pair(r1, i));
  }
  sort(c.begin(), c.end());
  long long int lt = 0, lk = 0;
  long long int str = 0, stp = 0;
  int flg = 0;
  for (long long int i = k - 1; i >= 0; i--) {
    if (i == k - 1) {
      long long int pos = c[i].first;
      long long int typ = c[i].second;
      sort(r.begin(), r.begin() + (pos + 1));
      lt = arr[typ];
      lk = typ;
      str = 0;
      stp = pos;
      if (arr[typ] == 2) {
        long long int tmp = str;
        str = stp;
        stp = tmp;
      }
      for (long long int j = n - 1; j > pos; j--) ans.push_back(r[j]);
    } else {
      long long int k_no = c[i].second;
      long long int pos = c[i].first;
      if (k_no > lk) {
        if (stp == str) {
          flg = 1;
          ans.push_back(r[str]);
          break;
        }
        if (stp > str) {
          for (long long int j = stp; j > (pos + str); j--) ans.push_back(r[j]);
          stp = pos + str;
          if (arr[k_no] != lt) {
            long long int tmp = stp;
            stp = str;
            str = tmp;
          }
          lt = arr[k_no];
          lk = k_no;
        } else {
          long long int val = str - (stp + pos);
          for (long long int j = stp; j < (stp + val); j++) ans.push_back(r[j]);
          stp = stp + val;
          if (arr[k_no] != lt) {
            long long int tmp = stp;
            stp = str;
            str = tmp;
          }
          lt = arr[k_no];
          lk = k_no;
        }
      }
    }
  }
  if (stp != str) {
    if (str < stp) {
      for (long long int i = stp; i >= str; i--) ans.push_back(r[i]);
    } else {
      for (long long int i = stp; i <= str; i++) ans.push_back(r[i]);
    }
  } else {
    if (flg == 0) ans.push_back(r[stp]);
  }
  for (long long int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << " ";
  return 0;
}
