#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int N = 200010;
int n, k, m;
int a[N], b[N], x[N], t[N];
int main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    b[i] = a[i];
  }
  int cnt = 1;
  int mx = 0;
  for (int i = 1; i <= m; i++) {
    int tp, r;
    cin >> tp >> r;
    mx = max(mx, r);
    while (cnt > 0 && r >= x[cnt]) cnt--;
    cnt++;
    x[cnt] = r;
    t[cnt] = tp;
  }
  sort(a + 1, a + 1 + mx);
  int l = 1;
  int r = mx;
  x[cnt + 1] = 0;
  for (int i = 1; i <= cnt; i++)
    for (int j = x[i]; j >= x[i + 1] + 1; j--)
      if (t[i] == 1)
        b[j] = a[r--];
      else
        b[j] = a[l++];
  for (int i = 1; i <= n; i++) cout << b[i] << " ";
  return 0;
}
