#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
template <typename T, bool MULTI = false, typename SIZE_T = int>
struct sms_mo {
  static_assert(std::is_integral<T>::value, "Not an integral type");
  static_assert(std::is_integral<SIZE_T>::value, "Not an integral type");
  struct node {
    node* ch[2];
    SIZE_T cnt;
    char d;
    T v, mi, ma;
    node(int d_, T v_, SIZE_T cnt_) : cnt(cnt_), d(d_), v(v_), mi(v), ma(v) {
      ch[0] = ch[1] = NULL;
    }
    node(node* x, bool b = true)
        : cnt(x->cnt), d(x->d), v(x->v), mi(x->mi), ma(x->ma) {
      if (b)
        ch[0] = x->ch[0], ch[1] = x->ch[1];
      else
        ch[0] = ch[1] = NULL;
    }
    void update() {
      if (!ch[0] ^ !ch[1]) {
        for (int i = 0; i < 2; i++)
          if (ch[i]) {
            node* tmp = ch[i];
            ch[0] = tmp->ch[0], ch[1] = tmp->ch[1];
            d = tmp->d, v = tmp->v;
            cnt = tmp->cnt, mi = tmp->mi, ma = tmp->ma;
            delete tmp;
            return;
          }
      }
      cnt = 0;
      mi = std::numeric_limits<T>::max(), ma = std::numeric_limits<T>::min();
      for (int i = 0; i < 2; i++)
        if (ch[i]) {
          cnt += ch[i]->cnt;
          mi = std::min(mi, ch[i]->mi), ma = std::max(ma, ch[i]->ma);
        }
    }
  };
  node* root;
  T N;
  char n;
  sms_mo() : root(NULL), N(0), n(0) {}
  sms_mo(T v) : sms_mo() {
    while (v >> n) n++, N = 2 * N + 1;
  }
  sms_mo(const sms_mo& t) : root(NULL), N(t.N), n(t.n) {
    if (!t.root) return;
    root = new node(t.root, false);
    std::vector<std::pair<node*, node*>> q = {{root, t.root}};
    while (q.size()) {
      auto [x, y] = q.back();
      q.pop_back();
      for (int i = 0; i < 2; i++)
        if (y->ch[i]) {
          x->ch[i] = new node(y->ch[i], false);
          q.emplace_back(x->ch[i], y->ch[i]);
        }
    }
  }
  sms_mo(std::initializer_list<T> v) : sms_mo() {
    for (T i : v) insert(i);
  }
  ~sms_mo() {
    std::vector<node*> q = {root};
    while (q.size()) {
      node* x = q.back();
      q.pop_back();
      if (!x) continue;
      q.push_back(x->ch[0]), q.push_back(x->ch[1]);
      delete x;
    }
  }
  friend void swap(sms_mo& a, sms_mo& b) {
    std::swap(a.root, b.root), std::swap(a.N, b.N), std::swap(a.n, b.n);
  }
  sms_mo& operator=(const sms_mo& v) {
    sms_mo tmp = v;
    swap(tmp, *this);
    return *this;
  }
  SIZE_T size() const { return root ? root->cnt : 0; }
  SIZE_T count(node* x) const { return x ? x->cnt : 0; }
  void clear() {
    sms_mo tmp;
    swap(*this, tmp);
  }
  void expand(T v) {
    while (v >> n) n++, N = 2 * N + 1;
  }
  std::vector<T> to_vector() {
    std::vector<T> ret;
    std::vector<node*> q = {root};
    while (q.size()) {
      node* x = q.back();
      q.pop_back();
      if (!x) continue;
      if (x->d == -1)
        for (int i = 0; i < x->cnt; i++) ret.push_back(x->v);
      else
        q.push_back(x->ch[1]), q.push_back(x->ch[0]);
    }
    return ret;
  }
  char msb(T v, char l, char r) {
    for (char i = r; i > l; i--)
      if (v >> i & 1) return i;
    return -1;
  }
  void cut(node* at, T v, char i, node* prev = NULL) {
    char d = msb(v ^ at->v, prev ? std::max(at->d, prev->d) : at->d, i);
    if (d == -1) {
      if (!prev or prev->d <= at->d) return;
      d = prev->d, v = ~at->v;
    }
    node* nxt = new node(at);
    at->ch[v >> d & 1] = NULL;
    at->ch[!(v >> d & 1)] = nxt;
    at->d = d;
  }
  node* insert(node* at, T v, SIZE_T qt, char i) {
    if (!at) return new node(-1, v, qt);
    cut(at, v, i);
    if (at->d == -1) {
      at->cnt += qt;
      at->mi = at->ma = v;
      if (!MULTI) at->cnt = 1;
      return at;
    }
    bool dir = v >> at->d & 1;
    at->ch[dir] = insert(at->ch[dir], v, qt, at->d - 1);
    at->update();
    return at;
  }
  void insert(T v, SIZE_T qt = 1) {
    if (qt <= 0) return erase(v, -qt);
    expand(v);
    root = insert(root, v, qt, n - 1);
  }
  node* erase(node* at, T v, SIZE_T qt, char i) {
    if (!at) return at;
    if (at->d == -1)
      at->cnt = at->cnt < qt ? 0 : at->cnt - qt;
    else {
      bool dir = v >> at->d & 1;
      at->ch[dir] = erase(at->ch[dir], v, qt, i - 1);
      at->update();
    }
    if (!at->cnt) delete at, at = NULL;
    return at;
  }
  void erase(T v, SIZE_T qt = 1) {
    if (v < 0 or v > N or !qt) return;
    if (qt < 0) insert(v, -qt);
    if (!count(v)) return;
    root = erase(root, v, qt, n - 1);
  }
  void erase_all(T v) {
    if (v < 0 or v > N or !count(v)) return;
    root = erase(root, v, std::numeric_limits<SIZE_T>::max(), n - 1);
  }
  SIZE_T count(node* at, T a, T b, T l, T r, char i) const {
    if (!at or b < l or r < a) return 0;
    if (a <= l and r <= b) return at->cnt;
    T m = l + (r - l) / 2;
    if (at->d < i) {
      if ((at->v >> i & 1) == 0)
        return count(at, a, b, l, m, i - 1);
      else
        return count(at, a, b, m + 1, r, i - 1);
    }
    return count(at->ch[0], a, b, l, m, i - 1) +
           count(at->ch[1], a, b, m + 1, r, i - 1);
  }
  SIZE_T count(T v) const { return count(root, v, v, 0, N, n - 1); }
  SIZE_T order_of_key(T v) { return count(root, 0, v - 1, 0, N, n - 1); }
  SIZE_T lower_bound(T v) { return order_of_key(v); }
  const T operator[](SIZE_T k) const {
    node* at = root;
    T l = 0, r = N;
    char i = n - 1;
    while (l < r) {
      T m = l + (r - l) / 2;
      if (at->d < i) {
        if ((at->v >> i & 1) == 0)
          r = m;
        else
          l = m + 1;
        i--;
        continue;
      }
      if (count(at->ch[0]) > k)
        at = at->ch[0], r = m;
      else {
        k -= count(at->ch[0]);
        at = at->ch[1];
        l = m + 1;
      }
      i--;
    }
    return l;
  }
  node* merge(node* l, node* r, char i) {
    if (!l or !r) return l ? l : r;
    cut(l, r->v, i, r), cut(r, l->v, i, l);
    if (l->d == -1) {
      if (MULTI) l->cnt += r->cnt;
      delete r;
      return l;
    }
    for (int j = 0; j < 2; j++) l->ch[j] = merge(l->ch[j], r->ch[j], l->d - 1);
    l->update(), delete r;
    return l;
  }
  void merge(sms_mo& s) {
    if (N > s.N) swap(*this, s);
    expand(s.N);
    root = merge(root, s.root, n - 1);
    s.root = NULL;
  }
  node* split(node*& x, SIZE_T k) {
    if (k <= 0 or !x) return NULL;
    node* ret = new node(x);
    ret->ch[0] = ret->ch[1] = NULL;
    ret->cnt = 0;
    if (x->d == -1)
      x->cnt -= k, ret->cnt += k, ret->mi = x->mi, ret->ma = x->ma;
    else {
      if (k <= count(x->ch[0]))
        ret->ch[0] = split(x->ch[0], k);
      else {
        ret->ch[1] = split(x->ch[1], k - count(x->ch[0]));
        std::swap(x->ch[0], ret->ch[0]);
      }
      ret->update(), x->update();
    }
    if (!x->cnt) delete x, x = NULL;
    return ret;
  }
  void split(SIZE_T k, sms_mo& s) {
    s.clear();
    s.root = split(root, std::min(k, size()));
    s.N = N, s.n = n;
  }
  void split_val(T k, sms_mo& s) { split(order_of_key(k), s); }
  T min() { return root->mi; };
  T max() { return root->ma; };
};
std::mt19937 dyn_array_rng(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename SIZE_T = int,
          typename SET = sms_mo<T, true, SIZE_T>>
struct dyn_array {
  static_assert(std::is_integral<T>::value, "Not an integral type");
  static_assert(std::is_integral<SIZE_T>::value, "Not an integral type");
  struct node {
    node *l, *r;
    int p;
    SIZE_T sz;
    bool rev, rev_lazy;
    SET val;
    T mi, ma;
    node(SET& v, bool rev_ = false)
        : l(NULL),
          r(NULL),
          p(dyn_array_rng()),
          sz(v.size()),
          rev(rev_),
          rev_lazy(0) {
      swap(val, v);
      mi = val.min(), ma = val.max();
    }
    node(node* x)
        : l(NULL),
          r(NULL),
          p(x->p),
          sz(x->sz),
          rev(x->rev),
          rev_lazy(x->rev_lazy),
          val(x->val),
          mi(x->mi),
          ma(x->ma) {}
    void prop() {
      if (rev_lazy) {
        rev ^= 1;
        std::swap(l, r);
        if (l) l->rev_lazy ^= 1;
        if (r) r->rev_lazy ^= 1;
      }
      rev_lazy = false;
    }
    void update() {
      sz = val.size();
      mi = val.min(), ma = val.max();
      if (l) sz += l->sz, mi = std::min(mi, l->mi), ma = std::max(ma, l->ma);
      if (r) sz += r->sz, mi = std::min(mi, r->mi), ma = std::max(ma, r->ma);
    }
  };
  node* root;
  dyn_array() { root = NULL; }
  dyn_array(const dyn_array& v) : root(NULL) {
    if (!v.root) return;
    root = new node(v.root);
    std::vector<std::pair<node*, node*>> q = {{root, v.root}};
    while (q.size()) {
      auto [x, y] = q.back();
      q.pop_back();
      if (y->l) {
        x->l = new node(y->l);
        q.emplace_back(x->l, y->l);
      }
      if (y->r) {
        x->r = new node(y->r);
        q.emplace_back(x->r, y->r);
      }
    }
  }
  dyn_array(std::initializer_list<T> v) : dyn_array() {
    for (T i : v) push_back(i);
  }
  ~dyn_array() {
    std::vector<node*> q = {root};
    while (q.size()) {
      node* x = q.back();
      q.pop_back();
      if (!x) continue;
      q.push_back(x->l), q.push_back(x->r);
      delete x;
    }
  }
  friend void swap(dyn_array& a, dyn_array& b) { std::swap(a.root, b.root); }
  dyn_array& operator=(const dyn_array& v) {
    dyn_array tmp = v;
    swap(tmp, *this);
    return *this;
  }
  void clear() {
    dyn_array tmp;
    swap(tmp, *this);
  }
  SIZE_T size(node* x) const { return x ? x->sz : 0; }
  SIZE_T size() const { return size(root); }
  void to_vector_rec(node* x, std::vector<T>& v) {
    if (!x) return;
    to_vector_rec(x->l, v);
    std::vector<T> at = x->val.to_vector();
    if (x->rev)
      v.insert(v.end(), at.rbegin(), at.rend());
    else
      v.insert(v.end(), at.begin(), at.end());
    to_vector_rec(x->r, v);
  }
  std::vector<T> to_vector() {
    std::vector<T> ret;
    to_vector_rec(root, ret);
    return ret;
  }
  void join(node* l, node* r, node*& i) {
    if (!l or !r) return void(i = l ? l : r);
    l->prop(), r->prop();
    if (l->p > r->p)
      join(l->r, r, l->r), i = l;
    else
      join(l, r->l, r->l), i = r;
    i->update();
  }
  void concat(dyn_array& v) {
    join(root, v.root, root);
    v.root = NULL;
  }
  void split(node* i, node*& l, node*& r, SIZE_T idx) {
    if (!i) return void(r = l = NULL);
    i->prop();
    if (size(i->l) + i->val.size() <= idx) {
      split(i->r, i->r, r, idx - size(i->l) - i->val.size());
      l = i;
    } else if (size(i->l) >= idx) {
      split(i->l, l, i->l, idx);
      r = i;
    } else {
      SET L;
      if (!i->rev)
        i->val.split(idx - size(i->l), L);
      else {
        i->val.split(i->val.size() - (idx - size(i->l)), L);
        swap(L, i->val);
      }
      node* novo = new node(L);
      novo->rev = i->rev;
      novo->l = i->l;
      i->l = NULL;
      novo->update();
      l = novo, r = i;
    }
    i->update();
  }
  void split(SIZE_T k, dyn_array& v) {
    v.clear();
    split(root, v.root, root, std::min(k, size()));
  }
  void push_back(T val, SIZE_T qt = 1) {
    SET v;
    v.insert(val, qt);
    join(root, new node(v), root);
  }
  T get(node* i, SIZE_T idx) const {
    i->prop();
    if (size(i->l) + i->val.size() <= idx)
      return get(i->r, idx - size(i->l) - i->val.size());
    if (size(i->l) > idx) return get(i->l, idx);
    if (!i->rev) return i->val[idx - size(i->l)];
    return i->val[i->val.size() - 1 - (idx - size(i->l))];
  }
  const T operator[](SIZE_T i) const { return get(root, i); }
  void update(SIZE_T idx, T val) {
    dyn_array L, M;
    split(idx + 1, M);
    M.split(idx, L);
    L.push_back(val);
    L.concat(*this);
    swap(*this, L);
  }
  void merge(node*& i, SET& v) {
    if (!i) return;
    i->prop();
    merge(i->l, v), merge(i->r, v);
    v.merge(i->val);
    delete i;
    i = NULL;
  }
  void sort(bool reverse = false) {
    if (!root) return;
    root->prop();
    merge(root->l, root->val);
    merge(root->r, root->val);
    root->rev = reverse;
    root->update();
  }
  void sort(SIZE_T l, SIZE_T r, bool reverse = false) {
    dyn_array L, M;
    split(r + 1, M);
    M.split(l, L);
    M.sort(reverse);
    L.concat(M);
    L.concat(*this);
    swap(*this, L);
  }
  void reverse() {
    if (root) root->rev_lazy ^= 1;
  }
  void reverse(SIZE_T l, SIZE_T r) {
    dyn_array L, M;
    split(r + 1, M);
    M.split(l, L);
    M.reverse();
    L.concat(M);
    L.concat(*this);
    swap(*this, L);
  }
  T min() { return root->mi; }
  T max() { return root->ma; }
  T rmq(SIZE_T l, SIZE_T r, bool get_max = false) {
    dyn_array L, M;
    split(r + 1, M);
    M.split(l, L);
    T ans = get_max ? M.max() : M.min();
    L.concat(M);
    L.concat(*this);
    swap(*this, L);
    return ans;
  }
  void slice(node*& x, T val, dyn_array& v) {
    if (!x or x->mi >= val) return;
    x->prop();
    slice(x->l, val, v);
    if (x->val.min() < val) {
      SET s;
      x->val.split_val(val, s);
      join(v.root, new node(s, x->rev), v.root);
    }
    slice(x->r, val, v);
    if (x->val.size())
      x->update();
    else {
      node* tmp = x;
      join(x->l, x->r, x);
      delete tmp;
    }
  }
  void slice(T val, dyn_array& v) {
    v.clear();
    slice(root, val, v);
  }
};
const int SHIFT = 1e9;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  dyn_array<int> v;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    v.push_back(SHIFT + x);
  }
  while (q--) {
    int t, r;
    cin >> t >> r;
    r--;
    v.sort(0, r, t - 1);
  }
  for (int i = 0; i < n; i++) cout << v[i] - SHIFT << " ";
  cout << '\n';
  exit(0);
}
