#include <bits/stdc++.h>
using namespace std;
int a[200004];
pair<int, int> b[200004];
vector<pair<int, int> > vec;
bool cmp(int i, int j) { return i < j; }
struct pot {
  int x;
  pot() {}
  pot(int t) { x = t; }
  bool operator<(const pot &other) const { return x > other.x; }
};
int main() {
  int n, m, u, v;
  cin >> n >> m;
  int mx = 0;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &u, &v);
    mx = max(mx, v);
    b[i] = make_pair(u, v);
  }
  int cur = -1;
  for (int i = m - 1; i >= 0; i--) {
    int v = b[i].second;
    if (v > cur) {
      vec.push_back(b[i]);
      cur = b[i].second;
    }
  }
  priority_queue<int> q1;
  priority_queue<pot> q2;
  for (int i = 1; i <= mx; i++) {
    q1.push(a[i]);
    q2.push(a[i]);
  }
  int len = vec.size() - 1;
  cur = vec[len].first;
  int i = len;
  while (i > 0) {
    int v = vec[i].first;
    if (v == 1) {
      int val = vec[i].second - vec[i - 1].second;
      while (val) {
        a[vec[i - 1].second + val] = q1.top();
        q1.pop();
        val--;
      }
    } else {
      int val = vec[i].second - vec[i - 1].second;
      while (val) {
        a[vec[i - 1].second + val] = q2.top().x;
        q2.pop();
        val--;
      }
    }
    i--;
  }
  if (vec[0].first == 1) {
    int l = 1;
    while (l <= vec[0].second) {
      a[l++] = q2.top().x;
      q2.pop();
    }
  } else {
    int l = 1;
    while (l <= vec[0].second) {
      a[l++] = q1.top();
      q1.pop();
    }
  }
  for (int j = 1; j <= n; j++) printf("%d ", a[j]);
}
