#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const ll mod = 1000000007;
const ll M = 1000000000000000000ll;
inline ll add(ll a, ll b) { return ((a % mod + b % mod) % mod); }
inline ll sub(ll a, ll b) { return ((a % mod - b % mod + mod) % mod); }
inline ll mult(ll a, ll b) { return (((a % mod) * (b % mod)) % mod); }
inline ll power(ll n, ll x) {
  ll p = 1;
  while (x != 0) {
    if (x % 2 == 0) {
      n = mult(n, n);
      x = x / 2;
    }
    p = mult(p, n);
    x--;
  }
  return p;
}
inline ll recurmult(ll a, ll b) {
  ll r = 0;
  while (b) {
    if (b & 1) r = add(r, a);
    a = mult(2, a);
    b >>= 1;
  }
  return r % mod;
}
ll c = 0;
vector<ll> query;
void recur(ll l, ll r, ll pt, ll v[], ll g) {
  if (pt == query.size()) {
    if (g == 1) {
      for (ll i = l; i <= r; i++) cout << v[i] << " ";
    } else {
      for (ll i = r; i >= l; i--) cout << v[i] << " ";
    }
  } else {
    if (g % 2 == 0) {
      recur(r - query[pt] + 1, r, pt + 1, v, !g);
      for (ll i = (r - query[pt]); i >= l; i--) cout << v[i] << " ";
    } else {
      recur(l, l + query[pt] - 1, pt + 1, v, !g);
      for (ll i = (l + query[pt]); i <= r; i++) cout << v[i] << " ";
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n, m;
  cin >> n >> m;
  ll v[n];
  for (ll i = 0; i < n; i++) cin >> v[i];
  vector<pair<ll, ll>> rec;
  ll l, r, mat, ma = 0, pt, s = 0, ri[200005] = {0};
  ri[0] = -1 * M;
  for (ll i = 0; i < m; i++) {
    ll t;
    cin >> t >> r;
    while (s > 0 && r >= ri[s - 1]) {
      rec.pop_back();
      s--;
    }
    rec.push_back({t, r});
    ri[s] = r;
    if (r >= ma) {
      ma = r;
      mat = t;
      pt = i;
    }
    s++;
  }
  ll mat1 = mat;
  for (ll i = 0; i < s; i++) {
    if (mat != rec[i].first) {
      mat = rec[i].first;
      query.push_back(rec[i].second);
    }
  }
  l = 0, r = ma - 1;
  if (mat1 == 1) {
    sort(v, v + ma);
    recur(l, r, 0, v, 1);
    for (ll i = r + 1; i < n; i++) cout << v[i] << " ";
  } else if (mat1 == 2) {
    sort(v, v + ma);
    recur(l, r, 0, v, 0);
    for (ll i = r + 1; i < n; i++) cout << v[i] << " ";
  }
}
