C

#include <bits/stdc++.h>

/****************************************
 *                                      *
 *  Made by:    KarleFKremen            *
 *  At:         5.2.16 00:41:50 ALMT    *
 *  For:        <contest name>          *
 *                                      *
 ****************************************/

// settings
    #define FILE "ancestor"
    #define USE_FREOPEN 0
    #define USE_LONG 0
    #define USE_IOSOPT 0
    #define INTERACT 0

// system
    #if USE_LONG
        typedef long long ll;
    #else
        typedef int ll;
    #endif
    #if USE_LONG
        typedef unsigned long long ull;
    #else
        typedef unsigned int ull;
    #endif
    typedef short sym;
    #if INTERACT
        #define eol endl
    #else
        #define eol '\n'
    #endif
    #define pb push_back
    #define mp make_pair
    #define p(a, b) pair < a, b >
    #define sq(x) (x * x)
    #define fi first
    #define se second
    #define rm erase
    #define ins insert
    #define rev(a) reverse(a.begin(), a.end())
    #define rs resize
    #define sz size
    #define M3 (ll)1e3
    #define M4 (ll)1e4
    #define M5 (ll)1e5
    #define M6 (ll)1e6
    #define M7 (ll)1e7
    #define M8 (ll)1e8
    #define M9 (ll)1e9
    #define stlprint(a) \
        for(auto __LEVEL_1_STL_ITERATOR = a.begin(); __LEVEL_1_STL_ITERATOR != a.end(); __LEVEL_1_STL_ITERATOR++) \
        { \
            cout << (*__LEVEL_1_STL_ITERATOR) << ' '; \
        }
    #define stlfor(a) for(auto it = a.begin(); it != a.end(); it++)

using namespace std;

int main()
{
    // ios{
        #if USE_IOSOPT
            ios_base::sync_with_stdio(false);
            cin.tie(0);
        #endif
        #if USE_FREOPEN
            freopen(FILE".in", "r", stdin);
            freopen(FILE".out", "w", stdout);
        #endif
    ll n, m;
    cin >> n >> m;
    ll a[M5 * 3];
    for(int i = 0; i < n; i++)
    {
        ll d;
        cin >> d;
        a[i] = d;
    }
    stack < p(sym, ll) > qr;
    for(int i = 0; i < m; i++)
    {
        sym x;
        ll r;
        cin >> x >> r;
        while((!qr.empty() && r >= qr.top().se))
            qr.pop();
        if(!(!qr.empty() && r <= qr.top().se && x == qr.top().fi))
            qr.push(mp(x, r));
    }
    vector < p(ll, ll) > rq;
    while(!qr.empty())
    {
        rq.pb(qr.top());
        qr.pop();
    }
    rev(rq);
    cout << "\n\n\n";
    stlfor(rq)
    {
        cout << it->fi << ' ' << it->se << endl;
        sort(a, a + it->se);
        if(it->fi == 2) reverse(a, a + it->se);
    }
    for(int i = 0; i < n; i++)
        cout << a[i] << ' ';
}