#include <bits/stdc++.h>
using namespace std;
const int INF = 2000000000;
const int MOD = 1000000007;
const long long L_MAX = 9223372036854775807;
const int I_MAX = 2147483647;
int A[200200], B[200200], R[200200], T[200200], maxR;
int main(int argc, const char **argv) {
  int n, m;
  while (~scanf("%d %d", &n, &m)) {
    for (int i = 0; i <= (n - 1); ++i) scanf("%d", A + i), B[i] = A[i];
    maxR = 0;
    for (int i = 0; i <= (m - 1); ++i) {
      int x, y;
      scanf("%d %d", &x, &y);
      maxR = max(maxR, y);
      T[y] = i + 1;
      R[y] = x;
    }
    sort(A, A + maxR);
    int x = 0;
    int y = maxR - 1, t = 0, j = 0;
    for (int i = (n - 1); i >= 0; --i) {
      if (T[i + 1] > t) j = R[i + 1], t = T[i + 1];
      if (t > 0) {
        if (j == 2)
          B[i] = A[x++];
        else
          B[i] = A[y--];
      }
    }
    for (int i = 0; i <= (n - 1); ++i) {
      printf("%d%s", B[i], i != (n - 1) ? " " : "\n");
    }
  }
  return 0;
}
