#include <bits/stdc++.h>
using namespace std;
int a[300000], b[300000];
struct node {
  int x, y, ra;
} c[300000];
bool cmp(int x, int y) { return x > y; }
struct edge {
  int x, y;
} d[300000];
bool comp(edge a, edge b) { return a.x > b.x; }
int vis[300000];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  int mark = -1000000000, flag = -1;
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &c[i].x, &c[i].y);
    if (c[i].y > mark) mark = c[i].y, flag = i;
    d[i].x = c[i].y, d[i].y = i;
  }
  sort(d, d + m, comp);
  for (int i = 0; i < m; i++) c[d[i].y].ra = i;
  if (c[flag].x == 1)
    sort(a, a + c[flag].y), mark = 1;
  else
    sort(a, a + c[flag].y, cmp), mark = 1;
  for (int i = 0; i < n; i++) b[i] = a[i];
  int l = 0, r = c[flag].y - 1;
  int RA = 0;
  for (int i = 0; i < flag + 1; i++) vis[c[i].ra] = 1;
  int res = c[flag].y;
  int mark2 = c[flag].x;
  for (int i = flag + 1; i < m; i++) {
    while (vis[RA]) RA++;
    vis[c[i].ra] = 1;
    if (c[i].ra != RA) continue;
    int x = c[i].x, y = c[i].y;
    if (mark) {
      for (int j = res - 1; j >= y; j--) b[j] = a[r], r--;
    } else {
      for (int j = res - 1; j >= y; j--) b[j] = a[l], l++;
    }
    if (x != mark2) mark ^= 1;
    mark2 = x;
    res = y;
  }
  if (mark) {
    for (int j = res - 1; j >= 0; j--) b[j] = a[r], r--;
  } else {
    for (int j = res - 1; j >= 0; j--) b[j] = a[l], l++;
  }
  for (int i = 0; i < n; i++) cout << b[i] << " ";
  cout << endl;
  return 0;
}
