#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9 + 7;
const int MAXA = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long INFLL = 9e18 + 7;
vector<int> numList, num, ans;
int n, m, a[MAXA];
pair<int, int> t[MAXA];
int mx = 0;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int(i) = (1); (i) <= (n); (i)++) cin >> a[i];
  for (int(i) = (1); (i) <= (m); (i)++) {
    cin >> t[i].second >> t[i].first;
    mx = max(mx, t[i].first);
  }
  for (int(i) = (1); (i) <= (mx); (i)++) num.push_back(a[i]);
  int cur = t[m].first;
  numList.push_back(m);
  for (int(i) = (m - 1); (i) >= (1); (i)--)
    if (t[i].first > cur) {
      cur = t[i].first;
      numList.push_back(i);
    }
  num.push_back(-INF);
  sort(num.begin(), num.end());
  int r = mx, l = 1;
  for (int(i) = (numList.size() - 2); (i) >= (0); (i)--) {
    for (int(j) = (t[numList[i + 1]].first); (j) >= (t[numList[i]].first + 1);
         (j)--) {
      a[j] = (t[numList[i + 1]].second == 1) ? num[r--] : num[l++];
    }
  }
  for (int(j) = (1); (j) <= (t[numList[0]].first); (j)++)
    a[j] = (t[numList[0]].second == 2) ? num[r--] : num[l++];
  for (int(i) = (1); (i) <= (n); (i)++) cout << a[i] << " ";
  return 0;
}
