#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 11, mod = 1e9 + 7;
const int INF1 = 2e9 + 11;
const long long INF2 = 2e18 + 11;
const int base = 500;
const int P = 31;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double EPS = 1e-12;
const double PI = acos(-1.0);
int n, m, a[N], t[N], r[N], mx, b[N];
int main() {
  if (fopen("queue"
            ".in",
            "r"))
    freopen(
        "queue"
        ".in",
        "r", stdin),
        freopen(
            "queue"
            ".out",
            "w", stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i += 1) cin >> a[i];
  int sz = 0;
  for (int i = 1; i <= m; i += 1) {
    int tt, rr;
    cin >> tt >> rr;
    while (rr >= r[sz] && sz) --sz;
    r[++sz] = rr;
    t[sz] = tt;
  }
  for (int i = 1; i <= r[1]; i += 1) b[i] = a[i];
  int curl = 1, curr = r[1];
  sort(b + 1, b + r[1] + 1);
  for (int i = 1; i <= sz; i += 1) {
    if (i == sz) {
      for (int j = r[i]; j >= 1; j -= 1)
        a[j] = (t[i] == 1 ? b[curr--] : b[curl++]);
      continue;
    }
    for (int j = r[i]; j >= r[i + 1] + 1; j -= 1)
      a[j] = (t[i] == 1 ? b[curr--] : b[curl++]);
  }
  for (int i = 1; i <= n; i += 1) cout << a[i] << " ";
  return 0;
}
