#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
int n, m, a[N], ans[N];
pair<int, int> p[N];
int b[N];
stack<int> s;
multiset<int> ms;
int main() {
  if (fopen("C.in", "r")) freopen("C.in", "r", stdin);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &p[i].first, &p[i].second);
  }
  int sz = 0;
  for (int i = 0; i < m; i++) {
    if (s.empty()) {
      s.push(i);
      continue;
    }
    while (!s.empty() && p[i].second >= p[s.top()].second) {
      s.pop();
    }
    s.push(i);
  }
  while (!s.empty()) {
    sz = s.top();
    b[p[s.top()].second - 1] = p[s.top()].first;
    s.pop();
  }
  for (int i = 0; i < p[sz].second; i++) {
    ms.insert(a[i]);
  }
  int cur = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (b[i]) cur = b[i];
    if (cur == 0) {
      ans[i] = a[i];
    } else if (cur == 1) {
      multiset<int>::iterator it = ms.end();
      it--;
      ans[i] = *it;
      ms.erase(it);
    } else {
      ans[i] = *ms.begin();
      ms.erase(ms.begin());
    }
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
  return 0;
}
