#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 100;
vector<int> vec;
map<int, int> mp, mp2;
int n, m, a[maxN], co = 1, x, y, c[maxN], co1, ans[maxN], l, r;
int main() {
  cin >> n >> m;
  for (long long int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (long long int i = 1; i <= m; i++) {
    cin >> y >> x;
    if (!mp[x]) {
      c[co] = x;
      co++;
    }
    mp[x] = i;
    mp2[x] = y;
  }
  sort(c + 1, c + co);
  for (long long int i = co - 1; i >= 1; i--) {
    if (mp[c[i]] > co1) {
      vec.push_back(c[i]);
      co1 = mp[c[i]];
    }
  }
  co = 1;
  sort(a + 1, a + vec[0] + 1);
  l = 1;
  r = vec[0];
  for (long long int i = n; i >= vec[0] + 1; i--) {
    ans[co] = a[i];
    co++;
  }
  if (vec.size() >= 2)
    for (long long int i = 0; i <= vec.size() - 2; i++) {
      if (mp2[vec[i]] == 1) {
        r -= vec[i] - vec[i + 1];
        for (long long int j = r + vec[i] - vec[i + 1]; j >= r + 1; j--) {
          ans[co] = a[j];
          co++;
        }
      } else {
        for (long long int j = l; j <= l + vec[i] - vec[i + 1] - 1; j++) {
          ans[co] = a[j];
          co++;
        }
        l += vec[i] - vec[i + 1];
      }
    }
  if (mp2[vec[vec.size() - 1]] == 1)
    for (long long int i = r; i >= l; i--) {
      ans[co] = a[i];
      co++;
    }
  else
    for (long long int i = l; i <= r; i++) {
      ans[co] = a[i];
      co++;
    }
  for (long long int i = n; i >= 1; i--) cout << ans[i] << " ";
  return 0;
}
