#include <bits/stdc++.h>
using namespace std;
int m, n, a[200005], ans[200005];
vector<pair<int, int> > p;
int main() {
  int order, num;
  int order1 = 0, order2 = 0;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &order, &num);
    pair<int, int> tmp = make_pair(order, num);
    while (!p.empty() && p[p.size() - 1].second <= num) {
      p.pop_back();
    }
    p.push_back(tmp);
  }
  int left = 0, right = p[0].second - 1;
  for (int i = right + 1; i < n; i++) {
    ans[i] = a[i];
  }
  sort(a, a + right + 1);
  p.push_back(make_pair(1, 0));
  for (int i = 0; i < p.size() - 1; i++) {
    order = p[i].first;
    num = p[i].second - p[i + 1].second;
    if (order == 1) {
      for (int j = p[i].second - 1; j > p[i + 1].second - 1; j--) {
        ans[j] = a[right];
        right--;
      }
    } else {
      for (int j = p[i].second - 1; j > p[i + 1].second - 1; j--) {
        ans[j] = a[left];
        left++;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i];
    if (i == n - 1)
      cout << endl;
    else
      cout << " ";
  }
  return 0;
}
