#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 1e2;
int n, m;
int a[maxn];
int b[maxn], c[maxn], t;
int res[maxn];
bool cmp(const int& a, const int& b) { return a > b; }
void print() {
  for (int i = 1; i <= n; i++) printf("%d%s", res[i], (i == n ? "\n" : " "));
}
int main(int argc, char* argv[]) {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= m; i++) {
    int bb, cc;
    scanf("%d%d", &bb, &cc);
    while (t && cc >= c[t]) t--;
    if (t && b[t] == bb) continue;
    c[++t] = cc;
    b[t] = bb;
  }
  for (int i = c[1] + 1; i <= n; i++) res[i] = a[i];
  if (!t) {
    print();
    return 0;
  }
  int l = 1, r = c[1], o = 1;
  if (b[1] == 1)
    sort(a + 1, a + 1 + c[1]);
  else
    sort(a + 1, a + 1 + c[1], cmp);
  for (int i = c[1], j = 2; i >= 1; i--) {
    if (j <= t && c[j] == i) {
      swap(l, r);
      o *= -1;
      j++;
    }
    res[i] = a[r], r -= o;
  }
  print();
  return 0;
}
