#include <bits/stdc++.h>
using namespace std;
bool cmp(int a, int b) {
  if (a > b) return true;
  return false;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int a[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  int b[m];
  int c[m];
  int d[m];
  int e[m];
  int l = 0;
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &b[i], &c[i]);
  }
  int qw = 0;
  for (int i = m - 1; i >= 0; i--) {
    if (c[i] > qw) {
      qw = c[i];
      d[l] = b[i];
      e[l++] = c[i];
    }
  }
  if (d[l - 1] == 1) sort(a, a + e[l - 1]);
  if (d[l - 1] == 2) sort(a, a + e[l - 1], cmp);
  int chk = 1;
  if (d[l - 1] == 2) {
    chk = 2;
  }
  int ans[n];
  int hi = n - 1;
  int x = 0;
  int y = n - 1;
  int l1 = l - 1;
  if (e[l - 1] == n) {
    l1--;
  }
  for (int i = n - 1; i >= 0; i--) {
    if (l1 >= 0) {
      if (i + 1 == e[l1]) {
        if (d[l - 1] == d[l1]) {
          hi = y;
          ans[i] = a[hi];
          chk = d[l - 1];
          hi--;
          y--;
        } else {
          hi = x;
          ans[i] = a[x];
          chk = d[l1];
          hi++;
          x++;
        }
        l1--;
      } else {
        ans[i] = a[hi];
        if (chk != d[l - 1]) {
          hi++;
          x++;
        } else {
          hi--;
          y--;
        }
      }
    } else {
      ans[i] = a[hi];
      if (chk != d[l - 1]) {
        hi++;
        x++;
      } else {
        hi--;
        y--;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    printf("%d ", ans[i]);
  }
}
