#include <bits/stdc++.h>
using namespace std;
bool cmp(int x, int y) { return x > y; }
int a[200010], b[200010], c[200010], tmp[200010], ans[200010], d[200010];
int main() {
  int i, j, n, m;
  while (~scanf("%d%d", &n, &m)) {
    for (i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      b[i] = a[i];
    }
    int len = 0;
    for (i = 0; i < m; i++) {
      scanf("%d%d", &d[i], &c[i]);
      while (len && c[i] >= ans[len - 1]) len--;
      tmp[len] = d[i];
      ans[len++] = c[i];
    }
    ans[len++] = 0;
    sort(b + 1, b + 1 + ans[0]);
    int ll = 1;
    int rr = ans[0];
    for (i = 1; i < len; i++) {
      for (j = ans[i - 1]; j > ans[i]; j--) {
        if (tmp[i - 1] == 1)
          a[j] = b[rr--];
        else
          a[j] = b[ll++];
      }
    }
    for (i = 1; i <= n; i++) {
      if (i == n)
        printf("%d\n", a[i]);
      else
        printf("%d ", a[i]);
    }
  }
  return 0;
}
