#include <bits/stdc++.h>   using namespace std;   template <typename T>   void chkmin(T &a, T b) {     a = min(a, b);   }   template <typename T>   void chkmax(T &a, T b) {     a = max(a, b);   }   inline int fread(void) {     int ret = 0, op = 1;     char ch = getchar();     for (; !isdigit(ch); ch = getchar())       if (ch ==  - ) op = -1;     for (; isdigit(ch); ch = getchar()) ret = (ret << 1) + (ret << 3) -  0  + ch;     return ret * op;   }   const int MAXN = 2e5 + 10;   const int MAXM = +10;   int n, m, a[MAXN], c[MAXN];   struct rec {     int t, r;     bool operator<(const rec &b) const { return r < b.r; }   } s[MAXN];   int top;   inline void init(void) {     n = fread(), m = fread();     for (int i = 1; i <= n; ++i) a[i] = fread(), c[i] = a[i];   }   int lt, rt;   inline void work(void) {     rec now;     top = 0;     for (int i = 1; i <= m; ++i) {       now.t = fread(), now.r = fread();       while (top && s[top] < now) --top;       s[++top] = now;     }     sort(c + 1, c + s[1].r + 1);     lt = 1;     rt = s[1].r;     ++top;     s[top].r = 0;     for (int i = 2; i <= top; ++i) {       if (s[i - 1].t == 1) {         for (int j = s[i - 1].r; j > s[i].r; --j) a[j] = c[rt--];       } else {         for (int j = s[i - 1].r; j > s[i].r; --j) a[j] = c[lt++];       }     }     for (int i = 1; i <= n; ++i) printf( %d  , a[i]);   }   int main() {     init();     work();     return 0;   }   