#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
long long fac[1000006];
inline long long exp(long long x, long long n) {
  long long r = 1;
  x = x;
  while (n) {
    if (n % 2) r = (r * x) % 1000000007;
    x = (x * x) % 1000000007;
    n = n / 2;
  }
  return r;
}
inline long long mmi(long long a) {
  return exp(a, 1000000007 - 2) % 1000000007;
}
inline long long fact(long long n) {
  long long res = 1;
  for (long long i = 1; i < (n + 1); ++i) {
    res = (res * i) % 1000000007;
  }
  return res;
}
inline void fact_a() {
  fac[0] = 1;
  fac[1] = 1;
  for (long long i = 1; i < (105); ++i) {
    fac[i] = (fac[i - 1] * i) % 1000000007;
  }
}
inline long long inv_fact(long long n) {
  long long par = fac[n];
  long long res = mmi(par);
  return res;
}
inline long long comb(long long n, long long r) {
  if (n == r && r == 0) return 1;
  if (n < r) return 0;
  return ((fac[n] * inv_fact(r)) % 1000000007 * inv_fact(n - r)) % 1000000007;
}
struct triplet {
  long long a, b, c;
};
bool operator<(const triplet &t1, const triplet &t2) {
  if (t1.a < t2.a) return true;
  if (t1.a == t2.a && t1.b < t2.b) return true;
  if (t1.a == t2.a && t1.b == t2.b && t1.c < t2.c) return true;
  return false;
}
pair<long long, pair<long long, long long> > ex_gcd(long long a, long long b) {
  if (b == 0) {
    return make_pair(a, make_pair(1, 0));
  }
  pair<long long, pair<long long, long long> > p = ex_gcd(b, a % b);
  long long gcd = p.first;
  long long x1 = p.second.first;
  long long y1 = p.second.second;
  long long x = y1;
  long long y = x1 - (a / b) * y1;
  return make_pair(gcd, make_pair(x, y));
}
long long prime[3000006];
long long spf_prime[3000006];
void sieve() {
  prime[1] = 1;
  for (long long i = 2; i * i <= 3000000; i++)
    if (prime[i] == 0)
      for (long long j = i * i; j <= 3000000; j += i) prime[j] = 1;
}
void spf() {
  for (long long i = 2; i * i <= 3000000; i++)
    if (!spf_prime[i])
      for (long long j = i * i; j <= 3000000; j += i)
        if (!spf_prime[j]) spf_prime[j] = i;
  for (long long i = 2; i <= 3000000; i++)
    if (!spf_prime[i]) spf_prime[i] = i;
}
long long getparent_BIT(long long idx) { return idx - (idx & -idx); }
long long getnext_BIT(long long idx) { return idx + (idx & -idx); }
long long getsum_BIT(long long idx, long long BIT[], long long n) {
  long long sum = 0;
  while (idx > 0) {
    sum += BIT[idx];
    idx = getparent_BIT(idx);
  }
  return sum;
}
void update_BIT(long long idx, long long BIT[], long long val, long long n) {
  while (idx <= n) {
    BIT[idx] += val;
    idx = getnext_BIT(idx);
  }
}
void build_BIT(long long BIT[], long long a[], long long n) {
  for (long long i = 0; i < (n); ++i) {
    update_BIT(i, BIT, a[i], n);
  }
}
void comp_lps(string s, long long lps[], long long n) {
  long long i = 1, j = 0;
  while (i < n) {
    if (s[i] == s[j]) {
      lps[i++] = ++j;
    } else {
      if (j != 0)
        j = lps[j - 1];
      else
        lps[i++] = 0;
    }
  }
}
void dfs_l(long long u, vector<vector<long long> > &adj, long long status[]) {
  if (status[u] == 1) return;
  status[u] = 1;
  for (long long i = 0; i < (adj[u].size()); ++i) dfs_l(adj[u][i], adj, status);
}
long long dij(long long u, long long n,
              vector<vector<pair<long long, long long> > > &adj,
              long long status[]) {
  long long dist[n];
  for (long long i = 0; i < (n); ++i) dist[i] = 1000000000;
  dist[0] = 0;
  priority_queue<pair<long long, long long>,
                 vector<pair<long long, long long> >,
                 greater<pair<long long, long long> > >
      q;
  q.push(make_pair(0, 0));
  while (!q.empty()) {
    pair<long long, long long> p;
    p = q.top();
    q.pop();
    long long x = p.second;
    long long w = p.first;
    if (status[x] == 1) continue;
    status[x] = 1;
    for (long long i = 0; i < (adj[x].size()); ++i) {
      long long ww = adj[x][i].first;
      long long y = adj[x][i].second;
      if (dist[x] + ww < dist[y]) {
        dist[y] = dist[x] + ww;
        q.push(make_pair(dist[y], y));
      }
    }
  }
  if (dist[n - 1] >= 1000000000) return -1;
  return dist[n - 1];
}
long long phi(long long n) {
  vector<long long> v;
  long long k = n;
  ;
  for (long long i = 2; i * i <= n; i++) {
    if (k % i == 0) {
      v.push_back(i);
      while (k % i == 0) k /= i;
    }
  }
  if (k > 1) v.push_back(k);
  long long ans = n;
  for (long long i = 0; i < (v.size()); ++i) ans -= (ans / v[i]);
  return ans;
}
struct trie {
  struct trie *left, *right;
  bool isend;
};
trie *get_trie() {
  trie *ptr = new trie;
  ptr->left = NULL;
  ptr->right = NULL;
  ptr->isend = false;
  return ptr;
}
bool isempty(trie *root) {
  if (root->left == NULL && root->right == NULL) return true;
  return false;
}
void insert_trie(trie *root, string key) {
  trie *ptr = root;
  for (long long i = 0; i < (key.size()); ++i) {
    if (key[i] == '0') {
      if (ptr->left == NULL) {
        ptr->left = get_trie();
      }
      ptr = ptr->left;
    } else {
      if (ptr->right == NULL) ptr->right = get_trie();
      ptr = ptr->right;
    }
  }
  ptr->isend = true;
}
trie *remove_trie(trie *root, string key, long long idx = 0) {
  if (root == NULL) return NULL;
  if (idx == key.size()) {
    if (isempty(root)) {
      delete (root);
      root = NULL;
    }
    return root;
  }
  if (key[idx] == '0')
    root->left = remove_trie(root->left, key, idx + 1);
  else
    root->right = remove_trie(root->right, key, idx + 1);
  if (isempty(root)) {
    delete (root);
    root = NULL;
  }
  return root;
}
long long search_trie(trie *root, string key) {
  trie *ptr = root;
  string s = "";
  for (long long i = 0; i < (key.size()); ++i) {
    if (key[i] == '0') {
      if (ptr->right != NULL) {
        ptr = ptr->right;
        s += '1';
      } else {
        ptr = ptr->left;
        s += '0';
      }
    } else {
      if (ptr->left != NULL) {
        ptr = ptr->left;
        s += '1';
      } else {
        ptr = ptr->right;
        s += '0';
      }
    }
  }
  long long res = 0;
  reverse(s.begin(), s.end());
  for (long long i = s.length() - 1; i >= (0); --i)
    res = res * 2 + (s[i] - '0');
  return res;
}
struct Comp {
  bool operator()(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    if (a.first != b.first) {
      return a.first < b.first;
    }
    return a.second > b.second;
  }
};
void dearr() {
  long long dar[1005];
  dar[0] = 1;
  dar[1] = 0;
  dar[2] = 1;
  for (long long i = 3; i < (1002); ++i) {
    dar[i] = (i - 1) * (dar[i - 1] + dar[i - 2]);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n, m;
  cin >> n >> m;
  long long a[n];
  for (long long i = 0; i < (n); ++i) cin >> a[i];
  stack<pair<long long, long long> > s;
  long long b[n];
  for (long long i = 0; i < (m); ++i) {
    long long t, r;
    cin >> t >> r;
    r--;
    while (!s.empty() && s.top().first <= r) {
      s.pop();
    }
    s.push(make_pair(r, t));
  }
  vector<pair<long long, long long> > v;
  while (!s.empty()) {
    v.push_back(s.top());
    s.pop();
  }
  sort(v.rbegin(), v.rend());
  vector<long long> u;
  long long val = n - 1 - v[0].first;
  for (long long i = 0; i < (n - val); ++i) u.push_back(a[i]);
  sort(u.begin(), u.end());
  for (long long i = n - val; i < (n); ++i) b[i] = a[i];
  for (long long i = 0; i < (u.size()); ++i) b[i] = u[i];
  long long ptr1 = 0;
  long long ptr2 = n - 1 - val;
  long long ptr3 = 0;
  long long ptr4 = n - 1 - val;
  long long last = -1;
  if (v[0].second == 1)
    last = 1;
  else
    last = 2;
  for (long long i = 1; i < (v.size()); ++i) {
    long long idx = v[i].first;
    long long op = v[i].second;
    long long num = v[i - 1].first - idx;
    if (last == 1) {
      while (num--) {
        a[ptr4] = b[ptr2];
        ptr2--;
        ptr4--;
      }
    } else {
      while (num--) {
        a[ptr4] = b[ptr1];
        ptr1++;
        ptr4--;
      }
    }
    last = op;
  }
  long long idx = v[v.size() - 1].first;
  vector<long long> y;
  for (long long i = ptr1; i < (ptr1 + idx + 1); ++i) y.push_back(b[i]);
  if (last == 1)
    sort(y.begin(), y.end());
  else
    sort(y.rbegin(), y.rend());
  for (long long i = 0; i < (idx + 1); ++i) a[i] = y[i];
  for (auto i : a) cout << i << " ";
  cout << "\n";
  ;
}
