1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <algorithm>
#include <cstdio>
#include <unordered_map>
#include <vector>

using namespace std;

void Compress(const vector<pair<int, int> >& v1, const vector<pair<int, int> >& v2, vector<pair<int, int> >* v3) {
  pair<pair<long long, long long>, int> current = make_pair(make_pair(v1[0].second, v2[0].second), 0);
  int i1 = 1;
  int i2 = 1;

  vector<pair<long long, int> > v4;
  v4.push_back(make_pair((current.first.first << 30) + current.first.second, current.second));

  while (i1 < v1.size() || i2 < v2.size()) {
    if (i1 == v1.size()) {
      current.first.second = v2[i2].second;
      current.second = v2[i2].first;
      ++i2;
    } else if (i2 == v2.size()) {
      current.first.first = v1[i1].second;
      current.second = v1[i1].first;
      ++i1;
    } else if (v1[i1].first == v2[i2].first) {
      current.first.first = v1[i1].second;
      current.first.second = v2[i2].second;
      current.second = v1[i1].first;
      ++i1;
      ++i2;
    } else if (v1[i1].first < v2[i2].first) {
      current.first.first = v1[i1].second;
      current.second = v1[i1].first;
      ++i1;
    } else {
      current.first.second = v2[i2].second;
      current.second = v2[i2].first;
      ++i2;
    }
    v4.push_back(make_pair((current.first.first << 30) + current.first.second, current.second));
  }

  vector<long long> v5;
  for (int i = 0; i < v4.size(); ++i) v5.push_back(v4[i].first);

  sort(v5.begin(), v5.end());
  v5.resize(unique(v5.begin(), v5.end()) - v5.begin());

  unordered_map<long long, int> m;
  for (int i = 0; i < v5.size(); ++i) m[v5[i]] = i;

  v3->clear();
  for (int i = 0; i < v4.size(); ++i) v3->push_back(make_pair(v4[i].second, m[v4[i].first]));
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<vector<pair<int, int> > > changes(n);
  for (int i = 0; i < n; ++i) {
    int t;
    scanf("%d", &t);
    changes[i].push_back(make_pair(0, t));
  }
  for (int i = 1; i < m; ++i) {
    int p, x;
    scanf("%d%d", &p, &x);
    changes[p - 1].push_back(make_pair(i, x));
  }

  int j = 0;
  for (int i = 0; i < changes.size(); ++i) if (changes[i].size() > 1) changes[j++] = changes[i];
  changes.resize(j);

  while (changes.size() > 1) {
    // Compress
    if (changes.size() % 2) changes.resize(changes.size() + 1, vector<pair<int, int> >(1, make_pair(0, 0)));
    for (int i = 0; 2 * i < changes.size(); ++i) Compress(changes[2 * i], changes[2 * i + 1], &changes[i]);
    changes.resize(changes.size() / 2);
  }

  // Read answer.
  vector<pair<int, int> > v;
  for (int i = 0; i < changes[0].size(); ++i) v.push_back(make_pair(changes[0][i].second, changes[0][i].first));
  sort(v.begin(), v.end());
  for (int i = 0; i < v.size(); ++i) {
    printf("%d", v[i].second + 1);
    if (i == v.size() - 1) printf("\n"); else printf(" ");
  }

  return 0;
}