#include <bits/stdc++.h>
using namespace std;
namespace impl {
using Random = std::mt19937;
}
inline impl::Random &randomEngine() {
  static std::random_device device;
  static impl::Random engine(device());
  return engine;
}
inline int randomInteger(int to) {
  std::uniform_int_distribution<int> d(0, to);
  return d(randomEngine());
}
inline int randInt(int from, int to) { return from + randomInteger(to - from); }
inline vector<int> randArr(int l, int min, int max) {
  vector<int> a;
  for (int i = 1; i <= l; i++) a.push_back(randInt(min, max));
  return a;
}
inline vector<pair<int, int>> randArrPair(int l, bool less, int min, int max) {
  vector<pair<int, int>> a;
  for (int i = 1; i <= l; i++) {
    int first = randInt(min, max);
    int second = randInt(min, max);
    if (less && first > second) {
      int t = first;
      first = second;
      second = t;
    }
    a.push_back(make_pair(first, second));
  }
  return a;
}
inline vector<vector<int>> rand2DArr(int r, int c, int min, int max) {
  vector<vector<int>> a(r, vector<int>());
  for (int i = 0; i < r; i++) a[i] = randArr(c, min, max);
  return a;
}
inline string randString(int l, string sample) {
  string toReturn = "";
  int size = ((int)(sample).size());
  while (l--) {
    int tmp = randInt(0, size);
    toReturn += sample[randInt(0, size - 1)];
  }
  return toReturn;
}
inline string randString(int l, bool lower, bool upper, bool number) {
  string sample = "";
  string lowList = "abcdefghijklmnopqrstuvwxyz";
  string upList = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  string numList = "0123456789";
  if (lower) sample += lowList;
  if (upper) sample += upList;
  if (number) sample += numList;
  return randString(l, sample);
}
inline vector<pair<int, int>> randTree(int n) {
  vector<pair<int, int>> toReturn;
  for (int i = 2; i <= n; i++) toReturn.push_back({i, randInt(1, i - 1)});
  return toReturn;
}
inline vector<pair<pair<int, int>, int>> randTree(int n, int min, int max) {
  vector<pair<int, int>> tree = randTree(n);
  vector<pair<pair<int, int>, int>> toReturn;
  for (pair<int, int> p : tree) {
    toReturn.push_back(
        make_pair(make_pair(p.first, p.second), randInt(min, max)));
  }
  return toReturn;
}
inline vector<pair<int, int>> randDAG(int v, int e) {
  set<string> set;
  vector<pair<int, int>> DAG;
  for (int i = 0; i < e; i++) {
    int tmp1 = -1;
    int tmp2 = -1;
    while (tmp1 == tmp2 ||
           set.find(to_string(tmp1) + to_string(tmp2)) != set.end()) {
      int pos = randInt(1, v - 1);
      tmp1 = pos;
      tmp2 = randInt(pos + 1, v);
    }
    DAG.push_back(make_pair(tmp1, tmp2));
    set.insert(to_string(tmp1) + to_string(tmp2));
  }
  return DAG;
}
inline vector<pair<pair<int, int>, int>> randDAG(int v, int e, int min,
                                                 int max) {
  vector<pair<int, int>> DAG = randDAG(v, e);
  vector<pair<pair<int, int>, int>> toReturn;
  for (pair<int, int> p : DAG) {
    toReturn.push_back(
        make_pair(make_pair(p.first, p.second), randInt(min, max)));
  }
  return toReturn;
}
inline string to_string(vector<pair<int, int>> list) {
  string res = "";
  for (int i = 0; i < ((int)(list).size()); i++) {
    pair<int, int> p = list[i];
    res += to_string(p.first) + " " + to_string(p.second);
    if (i != ((int)(list).size()) - 1) res += "\n";
  }
  return res;
}
inline string to_string(vector<pair<pair<int, int>, int>> list) {
  string res = "";
  for (int i = 0; i < ((int)(list).size()); i++) {
    pair<pair<int, int>, int> p = list[i];
    res += to_string(p.first.first) + " " + to_string(p.first.second) + " " +
           to_string(p.second);
    if (i != ((int)(list).size()) - 1) res += "\n";
  }
  return res;
}
inline string to_string(vector<int> list) {
  string res = "";
  for (int i = 0; i < ((int)(list).size()); i++) {
    res += to_string(list[i]) + " ";
  }
  return res;
}
inline string to_string(vector<vector<int>> list) {
  string res = "";
  for (int i = 0; i < ((int)(list).size()); i++) {
    res += to_string(list[i]) + " ";
    if (i != ((int)(list).size()) - 1) res += "\n";
  }
  return res;
}
using namespace std;
const int N = 1e5 + 1;
class Task631C {
 public:
  void solve(std::istream &in, std::ostream &out) {
    int n, m;
    in >> n >> m;
    vector<int> a(n + 1);
    vector<pair<int, int>> tmp(m + 1);
    vector<pair<int, int>> b;
    for (int i = 1; i <= n; i++) in >> a[i];
    for (int i = 1; i <= m; i++) in >> tmp[i].first >> tmp[i].second;
    int cur = 0;
    for (int i = m; i >= 1; i--) {
      if (tmp[i].second > cur) {
        b.push_back(tmp[i]);
        cur = tmp[i].second;
      }
    }
    reverse((b).begin(), (b).end());
    vector<int> list;
    cur = b[0].second;
    for (int i = 1; i <= cur; i++) list.push_back(a[i]);
    sort((list).begin(), (list).end());
    int l = 0, r = cur - 1;
    for (int i = 1; i < ((int)(b).size()); i++) {
      int diff = b[i - 1].second - b[i].second;
      if (b[i - 1].first == 1) {
        while (diff--) a[cur--] = list[r--];
      } else {
        while (diff--) a[cur--] = list[l++];
      }
    }
    if (b[((int)(b).size()) - 1].first == 1) {
      while (cur) {
        a[cur--] = list[r--];
      }
    } else {
      while (cur) {
        a[cur--] = list[l++];
      }
    }
    for (int i = 1; i <= n; i++) out << a[i] << " ";
    out << "\n";
  }
};
class TestCase {
 public:
  static constexpr bool printWAOnly = false;
  static constexpr int numTest = 0;
  static constexpr bool haveAns = true;
  static void generateTest(std::ostream &test) {
    int n = randInt(1, 100);
    int m = randInt(1, 100);
    vector<int> a = randArr(n, 1, 100);
    vector<pair<int, int>> b;
    for (int i = 1; i <= m; i++) {
      b.push_back(make_pair(randInt(1, 2), randInt(1, n)));
    }
    test << n << " " << m << "\n"
         << to_string(a) << "\n"
         << to_string(b) << "\n";
  }
  static void solve(std::istream &in, std::ostream &out) {
    int n, m;
    in >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) in >> a[i];
    for (int i = 1; i <= m; i++) {
      int c, r;
      in >> c >> r;
      if (c == 1)
        sort(a.begin(), a.begin() + r);
      else
        sort(a.begin(), a.begin() + r, greater<int>());
    }
    for (int i = 0; i < n; i++) {
      out << a[i] << " ";
    }
    out << "\n";
  }
};
class Checker {
 public:
  static constexpr double arg = 0.0;
  static bool check(std::istream &in, std::istream &out) {}
};
int main() {
  Task631C solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  out << fixed << setprecision(10);
  solver.solve(in, out);
  return 0;
}
