#include <bits/stdc++.h>
using namespace std;
long long n, m, lg;
long long a[200005];
long long fin[200005] = {0};
pair<long long, long long> cut[200005];
long long lrg[200005];
vector<long long> srt;
void fixit() {
  long long sshift = 0, lshift = 0, diff = 0;
  for (long long i = 0; i < m; i++) {
    if (cut[i].second <= lrg[i])
      continue;
    else {
      if (cut[i].first == 1) {
        diff = cut[i].second - lrg[i];
        for (long long j = 0; j < diff; j++) {
          fin[cut[i].second - j] = srt[lg - j - lshift];
        }
        lshift += diff;
      } else {
        diff = cut[i].second - lrg[i];
        for (long long j = 0; j < diff; j++) {
          fin[cut[i].second - j] = srt[sshift + j];
        }
        sshift += diff;
      }
    }
  }
}
int main() {
  long long t1, t2;
  cin >> n >> m;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (long long i = 0; i < m; i++) {
    cin >> t1 >> t2;
    t2--;
    cut[i] = make_pair(t1, t2);
  }
  lg = -1;
  for (long long i = m - 1; i >= 0; i--) {
    lrg[i] = lg;
    if (lg < cut[i].second) {
      lg = cut[i].second;
    }
  }
  for (long long i = 0; i <= lg; i++) {
    srt.push_back(a[i]);
  }
  sort(srt.begin(), srt.end());
  for (long long i = n - 1; i > lg; i--) {
    fin[i] = a[i];
  }
  fixit();
  for (long long i = 0; i < n; i++) cout << fin[i] << " ";
  cout << "\n";
}
