#include <bits/stdc++.h>
using namespace std;
int on(int n, int k) { return (n | (1 << k)); }
int off(int n, int k) { return (n - (n & (1 << k))); }
bool chck(int n, int k) { return (n & (1 << k)); }
int mini(int a, int b) {
  if (a < b) return a;
  return b;
}
int maxi(int a, int b) {
  if (a > b) return a;
  return b;
}
int n, m, k;
int a[201000];
vector<int> ans;
deque<pair<int, int> > dq;
void gen(int from, int to, int dir) {
  if (dq.empty()) {
    if (dir == 1) {
      for (int i = to; i >= from; i--) {
        ans.push_back(a[i]);
      }
    } else {
      for (int i = to; i <= from; i++) {
        ans.push_back(a[i]);
      }
    }
    return;
  }
  pair<int, int> now = dq.front();
  dq.pop_front();
  int ind = now.first;
  int nxt;
  if (from <= to) {
    nxt = from + ind - 1;
    for (int i = to; i > nxt; i--) {
      ans.push_back(a[i]);
    }
    gen(nxt, from, now.second);
  } else {
    nxt = from - ind + 1;
    for (int i = to; i < nxt; i++) {
      ans.push_back(a[i]);
    }
    gen(nxt, from, now.second);
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  int t, r;
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &t, &r);
    pair<int, int> now = make_pair(r, t);
    while (!dq.empty() && dq.back().first <= now.first) dq.pop_back();
    if (!dq.empty()) {
      if (dq.back().second != now.second) dq.push_back(now);
    } else {
      dq.push_back(now);
    }
  }
  pair<int, int> now = dq.front();
  dq.pop_front();
  sort(a + 1, a + now.first + 1);
  for (int i = n; i > now.first; i--) {
    ans.push_back(a[i]);
  }
  if (now.second == 1) {
    gen(1, now.first, 1);
  } else {
    gen(now.first, 1, 2);
  }
  for (int i = ans.size() - 1; i >= 0; i--) {
    printf("%d ", ans[i]);
  }
  puts("");
  return 0;
}
