#include <bits/stdc++.h>   using namespace std;   long long spf[2];   long long fac[2];   void sieve() {     spf[1] = 1;     for (long long i = 2; i < 2; i++) spf[i] = i;     for (long long i = 4; i < 2; i += 2) spf[i] = 2;     for (long long i = 3; i * i < 2; i++) {       if (spf[i] == i) {         for (long long j = i * i; j < 2; j += i)           if (spf[j] == j) spf[j] = i;       }     }   }   map<long long, long long> getfactor(long long a) {     map<long long, long long> m;     while (a > 1) {       m[spf[a]]++;       a /= spf[a];     }     return m;   }   long long power(long long x, long long y, long long p) {     long long res = 1;     x = x;     if (x == 0) return 0;     while (y > 0) {       if (y & 1) res = (res * x);       y = y >> 1;       x = (x * x);     }     return res;   }   long long gcd(long long a, long long b) {     if (a == 0) return b;     return gcd(b % a, a);   }   long long inverse(long long a, long long p) { return power(a, p - 2, p); }   long long ncr(long long n, long long r, long long p) {     if (r == 0) return 1;     return (fac[n] * inverse(fac[r], p) % p * inverse(fac[n - r], p) % p) % p;   }   void solve() {     long long n, m;     cin >> n >> m;     vector<pair<long long, long long> > v;     multiset<long long> s;     long long a[n + 1];     for (long long i = 1; i <= n; i++) {       cin >> a[i];       s.insert(a[i]);     }     long long flag = 0;     for (long long i = 0; i < m; i++) {       long long t, r;       cin >> t >> r;       if (v.size()) {         while (v[v.size() - 1].first <= r) {           v.pop_back();           if (v.size() == 0) break;         }       }       v.push_back(make_pair(r, t));     }     v.push_back(make_pair(0, 0));     long long j = 0, cur = 0;     for (long long i = n; i >= 1; i--) {       if (i == v[j].first) {         flag++;         cur = v[j].second;         j++;       }       if (flag) {         if (cur == 1) {           auto it = s.end();           it--;           a[i] = *it;           s.erase(it);         } else {           auto it = s.begin();           a[i] = *it;           s.erase(it);         }       } else         s.erase(s.find(a[i]));     }     for (long long i = 1; i <= n; i++) cout << a[i] <<    ;     cout <<   n ;   }   signed main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     long long t = 1;     while (t--) {       solve();     }   }   