#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool cmp(const int a, const int b)
{
    return a > b;
}
int n, m, a[200500], t[200500], r[200500], was2, was, last, last2, mx, mx2, point;
int main(){
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  for(int i = 0; i < m; i++){
    cin >> t[i] >> r[i];
    mx = max(mx, r[i]);
  }
  for(int i = n-1; i >= 0; i--){
    if(r[i] == mx){
      if(t[i] == 2){
        last2 = r[i];
        sort(a, a + r[i], cmp);
        was2 = 1;
      }
      else{
        last = r[i];
        sort(a, a + r[i]);
        was = 1;
      }
      point = i+1;
    }
  }
  for(int i = point; i < m; i++){
    if(t[i] == 2){
      if(t[i-1] == 2 && r[i] <= last2){
      }
      else if(was2 == 1 && r[i]<=last){
        int d = r[i]-1;
        for(int i = 0; i < r[i]/2; i++){
          swap(a[i], a[i+d]);
          d --;
        }
        last2 = r[i];
      }
      else{
        sort(a, a + r[i], cmp);
        was2 = 1;
        last2 = r[i];
      }
    }
    else{
      if(t[i-1] == 1 && last >= r[i]){
      }
      else if(was == 1 && r[i] <= last2){
        int d = r[i]-1;
        for(int i = 0; i < r[i]/2; i++){
          swap(a[i], a[i+d]);
          d --;
        }
        last = r[i];
      }
      else{
        sort(a, a + r[i]);
        was = 1;
        last = r[i];
      }
    }
  }
  for(int i = 0; i < n; i++){
    cout << a[i] << " ";
  }
  return 0;
}