#include <bits/stdc++.h>
using namespace std;
const int INF = int(1e9);
const double EPS = 1e-8;
struct debugger {
  template <typename T>
  debugger& operator,(const T& v) {
    cerr << v << " ";
    return *this;
  }
} dbg;
vector<pair<int, int> > arr;
vector<int> st;
int merge(int p1, int p2) {
  if (p1 == -1) return p2;
  if (p2 == -1) return p1;
  if (arr[p1].first > arr[p2].first) return p1;
  if (arr[p2].first > arr[p1].first) return p2;
  return p2;
}
void build(int p, int L, int R) {
  if (L == R) {
    st[p] = L;
    return;
  }
  int mid = (L + R) / 2;
  build(p * 2, L, mid);
  build(p * 2 + 1, mid + 1, R);
  st[p] = merge(st[p * 2], st[p * 2 + 1]);
}
int query(int p, int L, int R, int i, int j) {
  if (i > R || j < L) return -1;
  if (i <= L && j >= R) return st[p];
  int mid = (L + R) / 2;
  int p1 = query(p * 2, L, mid, i, j);
  int p2 = query(p * 2 + 1, mid + 1, R, i, j);
  return merge(p1, p2);
}
int main() {
  std::ios_base::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> seq(n);
  for (int i = 0; i < n; i++) cin >> seq[i];
  arr.resize(m);
  for (int i = 0; i < m; i++) {
    cin >> arr[i].second >> arr[i].first;
  }
  st.resize(4 * m);
  build(1, 0, m - 1);
  int id = query(1, 0, m - 1, 0, m - 1);
  pair<int, int> p = arr[id];
  sort(seq.begin(), seq.begin() + p.first);
  if (p.second == 2) {
    reverse(seq.begin(), seq.begin() + p.first);
  }
  int R = p.first - 1;
  vector<int> rev(n, 0);
  while (id != m - 1) {
    id = query(1, 0, m - 1, id + 1, m - 1);
    pair<int, int> np = arr[id];
    if (np.second != p.second) {
      rev[np.first - 1] = 1;
    }
    p = np;
  }
  vector<int> ans = seq;
  int lptr = 0, rptr = R;
  int crev = 0;
  for (int i = R; i >= 0; i--) {
    crev += rev[i];
    if (crev & 1) {
      assert(lptr <= n - 1);
      ans[i] = seq[lptr];
      lptr++;
    } else {
      assert(rptr >= 0);
      ans[i] = seq[rptr];
      rptr--;
    }
  }
  for (int x : ans) cout << x << ' ';
  cout << endl;
  return 0;
}
