#include <bits/stdc++.h>
using namespace std;
long long t[800040];
long long arr[200001];
bool marked[800040];
void push(long long v) {
  if (marked[v]) {
    t[v * 2] = t[v * 2 + 1] = t[v];
    marked[v * 2] = marked[v * 2 + 1] = true;
    marked[v] = false;
  }
}
void update(long long v, long long tl, long long tr, long long l, long long r,
            long long new_val) {
  if (l > r) return;
  if (l == tl && tr == r) {
    t[v] = new_val;
    marked[v] = true;
  } else {
    push(v);
    long long tm = (tl + tr) / 2;
    update(v * 2, tl, tm, l, min(r, tm), new_val);
    update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, new_val);
  }
}
long long get(long long v, long long tl, long long tr, long long pos) {
  if (tl == tr) {
    return t[v];
  }
  push(v);
  long long tm = (tl + tr) / 2;
  if (pos <= tm)
    return get(v * 2, tl, tm, pos);
  else
    return get(v * 2 + 1, tm + 1, tr, pos);
}
signed main() {
  long long n, m;
  cin >> n >> m;
  vector<long long> arr(n);
  for (long long i = 0; i < n; i++) {
    cin >> arr[i];
  }
  while (m--) {
    long long t, r;
    cin >> t >> r;
    r--;
    update(1, 0, n - 1, 0, r, t);
  }
  vector<long long> ano;
  for (long long i = 0; i < n; i++) {
    ano.push_back(get(1, 0, n - 1, i));
  }
  vector<long long> store;
  for (long long i = 0; i < n; i++) {
    if (ano[i] != 0) {
      store.push_back(arr[i]);
    } else
      break;
  }
  if (ano[store.size() - 1] == 1) {
    sort(store.begin(), store.end());
  } else {
    sort(store.rbegin(), store.rend());
  }
  list<long long> l;
  for (long long x : store) {
    l.push_back(x);
  }
  long long sz = store.size() - 1;
  long long x = ano[sz];
  arr[sz--] = l.back();
  l.pop_back();
  long long flag = 1;
  while (!l.empty()) {
    if (ano[sz] != x) {
      flag ^= 1;
      x = ano[sz];
    }
    if (flag == 1) {
      arr[sz--] = l.back();
      l.pop_back();
    } else {
      arr[sz--] = l.front();
      l.pop_front();
    }
  }
  for (long long x : arr) {
    cout << x << " ";
  }
  cout << endl;
}
