#include <bits/stdc++.h>   using ::std::cin;   using ::std::cout;   using ::std::endl;   using ::std::multiset;   using ::std::pair;   using ::std::vector;   int main() {     ::std::ios_base::sync_with_stdio(false);     int n, m;     cin >> n >> m;     vector<int> a(n);     for (int i = 0; i < n; ++i) cin >> a[i];     vector<pair<int, int>> tr;     for (int i = 0; i < m; ++i) {       int t, r;       cin >> t >> r;       while (!tr.empty() && tr.back().second <= r) tr.pop_back();       tr.push_back({t, r});     }     tr.push_back({-1, 0});     multiset<int> s;     for (int i = 0; i < tr[0].second; ++i) s.insert(a[i]);     for (int i = 0; i < static_cast<int>(tr.size()); ++i) {       for (int j = tr[i].second - 1; j >= tr[i + 1].second; --j) {         if (tr[i].first == 2) {           a[j] = *s.begin();           s.erase(s.begin());         } else {           a[j] = *--s.end();           s.erase(--s.end());         }       }     }     for (int x : a) cout << x <<    ;     cout << endl;     return 0;   }   