#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000009ll;
const long long INF = 9223372036854775807ll;
long long power(long long x, long long y, long long z) {
  long long t = 1;
  while (y > 0) {
    if (y % 2) {
      t = (t * x) % z;
    }
    x = (x * x) % z;
  }
  return t;
}
long long a[500005], P[500005];
int A[500005], B[500005];
int n, m, i, t, r;
vector<long long> W;
int main() {
  int mx = 0;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%lld", &a[i]), W.push_back(a[i]);
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &t, &r);
    if (t == 1) {
      A[r] = i;
      B[r] = 0;
    } else
      B[r] = i, A[r] = 0;
    mx = max(mx, r);
  }
  for (i = mx + 1; i <= n; i++) P[i] = a[i];
  for (i = mx; i >= 1; i--) {
    if (A[i] > B[i]) {
      B[i] = 0;
    } else
      A[i] = 0;
    if (A[i - 1] < B[i]) B[i - 1] = max(B[i], B[i - 1]);
    if (B[i - 1] < A[i]) A[i - 1] = max(A[i], A[i - 1]);
  }
  sort(W.begin(), W.begin() + mx);
  int l;
  r = mx - 1;
  l = 0;
  for (i = mx; i >= 1; i--) {
    if (A[i] > 0) {
      P[i] = W[r];
      r--;
    } else if (B[i] > 0) {
      P[i] = W[l];
      l++;
    }
  }
  for (i = 1; i <= n; i++) printf("%lld ", P[i]);
  return 0;
}
