#include <bits/stdc++.h>
using namespace std;
bool comp(int a, int b) {
  if (a < b) {
    return true;
  } else {
    return false;
  }
}
int main() {
  int n, k;
  cin >> n >> k;
  deque<int> nums;
  vector<int> nums2;
  for (int i = 0; i < n; i++) {
    int in;
    cin >> in;
    nums.push_back(in);
  }
  vector<pair<int, int> > v;
  for (int i = 0; i < k; i++) {
    int in1, in2;
    cin >> in1 >> in2;
    int index = v.size() - 1;
    while (!v.empty() && in2 >= v[index].second) {
      v.pop_back();
      index--;
    }
    v.push_back({in1, in2});
  }
  for (int i = 0; i < v[0].second; i++) {
    nums2.push_back(nums[i]);
  }
  if (v[0].first == 1) {
    sort(nums2.begin(), nums2.end());
  } else {
    sort(nums2.begin(), nums2.end(), comp);
  }
  v.push_back({0, 0});
  int right = v[0].second - 1, left = 0;
  for (int i = 1; i < v.size(); i++) {
    for (int j = v[i - 1].second; j > v[i].second; j--) {
      if (v[i - 1].first == 1) {
        nums[j - 1] = nums2[right];
        right--;
      } else {
        nums[j - 1] = nums2[left];
        left++;
      }
    }
  }
  for (int i = 0; i < nums.size(); i++) {
    cout << nums[i] << " ";
  }
}
