#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long powmod(long long a, long long b, long long MOD) {
  long long ans = 1;
  while (b) {
    if (b % 2) ans = ans * a % MOD;
    a = a * a % MOD;
    b /= 2;
  }
  return ans;
}
const int N = 2e5 + 11;
int n, m, a[N];
int t[N], r[N];
int q[N], top;
int ans[N], tmp[N], RR;
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i], ans[i] = a[i];
  for (int i = 1; i <= m; i++) cin >> t[i] >> r[i], RR = max(RR, r[i]);
  for (int i = 1; i <= m; i++) {
    while (top && r[q[top]] <= r[i]) top--;
    q[++top] = i;
  }
  for (int i = 1; i <= RR; i++) tmp[i] = a[i];
  sort(tmp + 1, tmp + 1 + RR);
  int L = 1, R = RR;
  for (int i = 1; i <= top; i++) {
    if (t[q[i]] == 1) {
      for (int j = r[q[i]]; j > (i < top ? r[q[i + 1]] : 0); j--) {
        ans[j] = tmp[R--];
      }
    } else {
      for (int j = r[q[i]]; j > (i < top ? r[q[i + 1]] : 0); j--) {
        ans[j] = tmp[L++];
      }
    }
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
  return 0;
}
