#include <bits/stdc++.h>
using namespace std;
using namespace std;
const int N = 500500;
int a[N];
int n, m;
int t[N], l[N];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  vector<int> v;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &t[i], &l[i]);
    while (true) {
      if ((int)v.size() == 0) {
        break;
      }
      int idx = v.back();
      if (l[idx] <= l[i]) {
        v.pop_back();
      } else
        break;
    }
    v.push_back(i);
  }
  vector<int> ans;
  multiset<int> ms;
  multiset<int>::iterator it;
  for (int i = 1; i <= l[v[0]]; i++) {
    ms.insert(a[i]);
  }
  int cur = t[v[0]];
  for (int i = 1; i < (int)v.size(); i++) {
    int dl = abs(l[v[i]] - l[v[i - 1]]);
    while (dl--) {
      if (cur == 2) {
        ans.push_back(*ms.begin());
        ms.erase(ms.begin());
      } else {
        it = ms.end();
        --it;
        ans.push_back(*it);
        ms.erase(it);
      }
    }
    cur = t[v[i]];
  }
  int dl = (int)ms.size();
  while (dl--) {
    if (cur == 2) {
      ans.push_back(*ms.begin());
      ms.erase(ms.begin());
    } else {
      it = ms.end();
      --it;
      ans.push_back(*it);
      ms.erase(it);
    }
  }
  for (int i = (int)ans.size() - 1; i >= 0; --i) printf("%d ", ans[i]);
  for (int j = l[v[0]] + 1; j <= n; j++) printf("%d ", a[j]);
  puts("");
  return 0;
}
