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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <bits/stdc++.h>
using namespace std;

const int MAX = 500000;

vector<int> cnt;
vector<int> st;

struct tree {
  tree(int n) {
    for(size = 1; size < n; size *= 2);
    V.resize(2*size);
    val.resize(2*size);
    all.resize(size+1);
  }

  void set(int x, int v) {
    val[x+size] = v;
  }

  void add(int x, pair<int,int> v) {
    V[x+size].push_back(v);
  }

  void build() {
    for (int k = size / 2; k > 0; k /= 2) {
      auto &al = all[k];
      for (int t = k; t < 2 * k; t++) {
        int i = 0, j = 0;
        int hi = val[2*t], hj = val[2*t+1];
        al.push_back({hi, hj});
        // printf("%d %d: %d %d\n", k, t, hi, hj);
        while (i < (int)V[2*t].size() || j < (int)V[2*t+1].size()) {
          if (i == (int)V[2*t].size()) {
            hj = V[2*t+1][j++].second;
          } else if (j == (int)V[2*t+1].size()) {
            hi = V[2*t][i++].second;
          } else {
            if (V[2*t][i].first < V[2*t+1][j].first) {
              hi = V[2*t][i++].second;
            } else {
              hj = V[2*t+1][j++].second;
            }
          }
          al.push_back({hi, hj});
          // printf("%d %d: %d %d\n", k, t, hi, hj);
        }
      }
      {
        if (k == size / 2) {
          sort(al.begin(), al.end());
        } else {
          int mx = 0;
          for (auto const& p : al) {
            mx = max(mx, max(p.first, p.second));
          }
          cnt.assign(mx+1, 0);
          auto tmp = al;
          for (auto const& p : al) {
            cnt[p.second]++;
          }
          for (int i = 0; i < mx; i++) {
            cnt[i+1] += cnt[i];
          }
          for (int i = 0; i < (int)al.size(); i++) {
            tmp[--cnt[al[i].second]] = al[i];
          }
          cnt.assign(mx+1, 0);
          for (auto const& p : tmp) {
            cnt[p.first]++;
          }
          for (int i = 0; i < mx; i++) {
            cnt[i+1] += cnt[i];
          }
          for (int i = (int)al.size() - 1; i >= 0; i--) {
            al[--cnt[tmp[i].first]] = tmp[i];
          }
        }
      }
      al.erase(unique(al.begin(), al.end()), al.end());
      if (k != size / 2) {
        st.assign(al.back().first+2, -1);
        st.back() = al.size();
        for (int i = (int)al.size()-1; i >= 0; i--) {
          st[al[i].first] = i;
        }
        for (int i = (int)st.size()-2; i >= 0; i--) {
          if (st[i] == -1) {
            st[i] = st[i+1];
          }
        }
      }
      // printf("%d %d\n", k, (int)al.size());
      for (int t = k; t < 2 * k; t++) {
        // V[t].reserve(V[2*t].size() + V[2*t+1].size());
        auto b = al.begin();
        auto e = al.end();
        if (k != size / 2) {
          b = al.begin() + st[val[2*t]];
          e = al.begin() + st[val[2*t]+1];
        }
        val[t] = lower_bound(b, e, pair<int,int>{val[2*t], val[2*t+1]}) - al.begin();
        // printf("val %d = %d\n", t, val[t]);
        int i = 0, j = 0;
        int hi = val[2*t], hj = val[2*t+1];
        // printf("%d %d: %d %d\n", k, t, hi, hj);
        while (i < (int)V[2*t].size() || j < (int)V[2*t+1].size()) {
          int tim;
          if (i == (int)V[2*t].size()) {
            tim = V[2*t+1][j].first;
            hj = V[2*t+1][j++].second;
          } else if (j == (int)V[2*t+1].size()) {
            tim = V[2*t][i].first;
            hi = V[2*t][i++].second;
          } else {
            if (V[2*t][i].first < V[2*t+1][j].first) {
              tim = V[2*t][i].first;
              hi = V[2*t][i++].second;
            } else {
              tim = V[2*t+1][j].first;
              hj = V[2*t+1][j++].second;
            }
          }
          b = al.begin();
          e = al.end();
          if (k != size / 2) {
            b = al.begin() + st[hi];
            e = al.begin() + st[hi+1];
          }
          int h = lower_bound(b, e, pair<int,int>{hi, hj}) - al.begin();
          V[t].push_back({tim, h});
          // printf("pb %d %d: %d %d\n", k, t, tim, h);
        }
      }
    }
  }

  int root_hash(int c) {
    int ret;
    if (c == 0) {
      ret = val[1];
    } else {
      ret = V[1][c-1].second;
    }
    return ret;
  }

  vector<vector<pair<int,int>>> V;
  vector<int> val;
  vector<vector<pair<int, int>>> all;
  int size;
};

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  tree T(n);
  for (int i = 0; i < n; i++) {
    int t;
    scanf("%d", &t);
    T.set(i, t);
  }
  for (int i = 1; i < m; i++) {
    int x, t;
    scanf("%d %d", &x, &t);
    x--;
    T.add(x, {i, t});
  }
  T.build();
  vector<pair<int,int>> P;
  P.push_back({T.root_hash(0), 0});
  for (int i = 1; i < m; i++) {
    P.push_back({T.root_hash(i), i});
  }
  sort(P.begin(), P.end());
  for (auto p : P) {
    printf("%d ", p.second+1);
  }
  printf("\n");
}