#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
int a[N];
int cnt, sta[N], ot[N];
void dfs(int l, int r, int o) {
  if (o == cnt) {
    if (ot[o] == 1)
      for (int i = l; i <= r; ++i) printf("%d ", a[i]);
    else
      for (int i = r; i >= l; --i) printf("%d ", a[i]);
    return;
  }
  if (ot[o] == 1) {
    dfs(l, l + sta[o + 1] - 1, o + 1);
    for (int i = l + sta[o + 1]; i <= r; ++i) printf("%d ", a[i]);
  } else {
    dfs(r - sta[o + 1] + 1, r, o + 1);
    for (int i = r - sta[o + 1]; i >= l; --i) printf("%d ", a[i]);
  }
}
int main() {
  int n, m, inot, inr;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &inot, &inr);
    for (; cnt > 0 && sta[cnt] <= inr; --cnt)
      ;
    ++cnt, sta[cnt] = inr, ot[cnt] = inot;
  }
  sort(a + 1, a + sta[1] + 1);
  dfs(1, sta[1], 1);
  for (int i = sta[1] + 1; i <= n; ++i) printf("%d ", a[i]);
  return 0;
}
