#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
int a[200005], pos[200005];
pair<int, int> s[200005];
int stop = 0;
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    pos[i] = i;
    cin >> a[i];
  }
  for (int i = 1; i <= m; ++i) {
    pair<int, int> l;
    cin >> l.first >> l.second;
    while (stop != 0 && s[stop - 1].second < l.second) stop--;
    s[stop++] = l;
  }
  if (stop != 0) {
    int l = 1, r = s[0].second, k = s[0].second, i = 0;
    sort(a + 1, a + s[0].second + 1);
    s[stop + 1].second = s[stop].second = 0;
    while (i != stop) {
      if (k > s[i + 1].second) {
        if (s[i].first == 1)
          pos[k--] = r--;
        else
          pos[k--] = l++;
      } else
        i++;
    }
  }
  for (int i = 1; i <= n; ++i) cout << a[pos[i]] << " ";
  cout << endl;
  return 0;
}
