#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m, a[maxn], ans[maxn];
pair<int, int> p[maxn];
priority_queue<int> que1;
priority_queue<int, vector<int>, greater<int> > que2;
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int x, y, top = 0;
  for (int i = 1; i <= m; i++) {
    cin >> x >> y;
    if (i == 1)
      p[++top].first = x, p[top].second = y;
    else {
      while (top && y >= p[top].second) top--;
      p[++top].first = x, p[top].second = y;
    }
  }
  int pos = n;
  while (pos && pos > p[1].second) ans[pos] = a[pos], pos--;
  for (int i = 1; i <= pos; i++) que1.push(a[i]), que2.push(a[i]);
  p[top + 1].first = 1;
  p[top + 1].second = 0;
  for (int i = 2; i <= top + 1; i++) {
    if (p[i - 1].first == 1) {
      while (pos && pos > p[i].second) ans[pos] = que1.top(), que1.pop(), pos--;
    } else {
      while (pos && pos > p[i].second) ans[pos] = que2.top(), que2.pop(), pos--;
    }
  }
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]);
}
