#include <bits/stdc++.h>
using namespace std;
const long long int Maxn3 = 1e3 + 10;
const long long int Maxn4 = 1e4 + 10;
const long long int Maxn5 = 1e5 + 10;
const long long int Maxn6 = 1e6 + 10;
const long long int Maxn7 = 1e7 + 10;
const long long int Maxn8 = 1e8 + 10;
const long long int Maxn9 = 1e9 + 10;
const long long int Maxn18 = 1e18 + 10;
const long long int Mod1 = 1e7 + 7;
const long long int Mod2 = 1e9 + 7;
const long long int LLMax = LLONG_MAX;
const long long int LLMin = LLONG_MIN;
const long long int INTMax = INT_MAX;
const long long int INTMin = INT_MIN;
long long int mn = LLMax, mx = LLMin;
long long int t[Maxn6], r[Maxn6], a[Maxn6], b[Maxn6];
int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    b[i] = a[i];
  }
  int s = 0;
  for (int i = 0; i < m; i++) {
    int tt, rr;
    cin >> tt >> rr;
    while (s and rr >= r[s - 1]) s--;
    t[s] = tt;
    r[s] = rr;
    s++;
  }
  r[s++] = 0;
  int l = 1, k = r[0];
  sort(b + 1, b + r[0] + 1);
  for (int i = 1; i < s; i++)
    for (int j = r[i - 1]; j > r[i]; j--)
      if (t[i - 1] == 1)
        a[j] = b[k--];
      else
        a[j] = b[l++];
  for (int i = 1; i <= n; i++) cout << a[i] << ' ';
  return 0;
}
