#include <bits/stdc++.h>
using namespace std;
struct manager {
  int ith, ti, ri;
};
manager man[200111];
int cmpMan(manager m1, manager m2) {
  if (m1.ri != m2.ri)
    return m1.ri > m2.ri;
  else
    return m1.ith > m2.ith;
}
int nums[201000];
int rets[201000];
int cmpNonDes(int a, int b) { return a < b; }
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int i, j;
  for (i = 1; i <= n; i++) scanf("%d", &nums[i]);
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &man[i].ti, &man[i].ri);
    man[i].ith = i;
  }
  sort(man + 1, man + 1 + m, cmpMan);
  sort(nums + 1, nums + 1 + man[1].ri, cmpNonDes);
  for (i = man[1].ri + 1; i <= n; i++) rets[i] = nums[i];
  int left = 1, right = man[1].ri, lastIth = 1;
  for (i = 2; i <= m; i++) {
    if (man[i].ri == man[i - 1].ri) continue;
    if (man[i].ith < man[lastIth].ith) continue;
    if (man[lastIth].ti == 2)
      for (j = man[lastIth].ri; j > man[i].ri; j--, left++)
        rets[j] = nums[left];
    else
      for (j = man[lastIth].ri; j > man[i].ri; j--, right--)
        rets[j] = nums[right];
    lastIth = i;
  }
  if (man[lastIth].ti == 2)
    for (j = man[lastIth].ri; j > 0; j--, left++) rets[j] = nums[left];
  else
    for (j = man[lastIth].ri; j > 0; j--, right--) rets[j] = nums[right];
  for (i = 1; i <= n; i++) printf("%d ", rets[i]);
  printf("\n");
  return 0;
}
