#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T bpow(T p, T e) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p);
    p = (p * p);
  }
  return (T)ret;
}
int toInt(string s) {
  int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
int toLlint(string s) {
  long long int sm;
  stringstream ss(s);
  ss >> sm;
  return sm;
}
const double eps = 1e-9;
int ts, kk = 1;
char qr[200005];
int ctm[200005];
int n, m, a[200005], b[200005], rs[200005];
int tr[2][200005 * 4];
void bld(int i, int s, int e) {
  if (s == e) {
    scanf("%d", &a[s]);
    b[s] = a[s];
    tr[0][i] = tr[1][i] = s;
    return;
  }
  int md = (s + e) / 2;
  bld(i * 2 + 1, s, md);
  bld(i * 2 + 2, md + 1, e);
  if (a[tr[0][i * 2 + 1]] >= a[tr[0][i * 2 + 2]])
    tr[0][i] = tr[0][i * 2 + 1];
  else
    tr[0][i] = tr[0][i * 2 + 2];
  if (a[tr[1][i * 2 + 1]] <= a[tr[1][i * 2 + 2]])
    tr[1][i] = tr[1][i * 2 + 1];
  else
    tr[1][i] = tr[1][i * 2 + 2];
}
int y;
int qrymx(int i, int s, int e) {
  if (e <= y) return tr[0][i];
  int md = (s + e) / 2;
  int k = qrymx(i * 2 + 1, s, md);
  if (md < y) {
    int q = qrymx(i * 2 + 2, md + 1, e);
    if (a[k] < a[q]) k = q;
  }
  return k;
}
int qrymn(int i, int s, int e) {
  if (e <= y) return tr[1][i];
  int md = (s + e) / 2;
  int k = qrymn(i * 2 + 1, s, md);
  if (md < y) {
    int q = qrymn(i * 2 + 2, md + 1, e);
    if (b[k] > b[q]) k = q;
  }
  return k;
}
void updt(int i, int s, int e, int p) {
  if (s == e) {
    a[s] = -2000000000;
    b[s] = 2000000000;
    return;
  }
  int md = (s + e) / 2;
  if (p <= md)
    updt(i * 2 + 1, s, md, p);
  else
    updt(i * 2 + 2, md + 1, e, p);
  if (a[tr[0][i * 2 + 1]] >= a[tr[0][i * 2 + 2]])
    tr[0][i] = tr[0][i * 2 + 1];
  else
    tr[0][i] = tr[0][i * 2 + 2];
  if (b[tr[1][i * 2 + 1]] <= b[tr[1][i * 2 + 2]])
    tr[1][i] = tr[1][i * 2 + 1];
  else
    tr[1][i] = tr[1][i * 2 + 2];
}
int main() {
  int t = 1, i, j, k;
  scanf("%d%d", &n, &m);
  bld(0, 1, n);
  while (m--) {
    scanf("%d%d", &j, &k);
    qr[k] = j;
    ctm[k] = t++;
  }
  int ls = 0, x = -1;
  ;
  y = -1;
  for (i = n; i > 0; i--) {
    if (qr[i] != 0) {
      if (y == -1)
        y = i, ls = qr[i], x = ctm[i];
      else {
        if (x < ctm[i]) {
          x = ctm[i];
          ls = qr[i];
        }
      }
    }
    if (ls == 0) {
      rs[i] = a[i];
      continue;
    } else if (ls == 1) {
      k = qrymx(0, 1, n);
      rs[i] = a[k];
    } else {
      k = qrymn(0, 1, n);
      rs[i] = b[k];
    }
    updt(0, 1, n, k);
  }
  printf("%d", rs[1]);
  for (i = 2; i <= n; i++) printf(" %d", rs[i]);
  return 0;
}
