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
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int inf = 2e9;

vector<vector<pii> > c;
vector<int> result;
list<pii> spans;
int span_count;

int val_at(int x, int level) {
	auto xx = upper_bound(c[level].begin(), c[level].end(), pii(x, inf));
	return (--xx)->second;
}

list<pii>::iterator span_sort(int level, list<pii>::iterator &spanit) {
	pii span = *spanit;
	auto after_it = spans.erase(spanit);
	if (span.first == span.second) {
		return after_it;
	}

	set<pii> v;
	for (int i = span.first; i <= span.second; i++) {
		int vv = val_at(result[i], level);
		v.insert(pii(vv, result[i]));
	}

	int offset = 0;
	int span_s = 0;
	int span_v = v.begin()->first;
	for (auto it = v.begin(); it != v.end(); it++) {
		result[span.first+offset] = it->second;
		if (it->first != span_v) {
			if (span_s < offset-1) {
				spans.insert(after_it, pii(span.first+span_s, span.first+offset-1));
			}
			span_s = offset;
			span_v = it->first;
		}
		offset++;
	}

	spans.insert(after_it, pii(span.first+span_s, span.first+offset-1));

	return after_it;
}

void lsort(int level) {
	auto it = spans.begin();

	while (it != spans.end()) {
		it = span_sort(level, it);
	}
}

int main() {
	ios_base::sync_with_stdio(0);

	int n, m;
	cin >> n >> m;

	vector<pair<int, pii> > values;
	c.resize(n);
	result.resize(m);

	int tmp, tmp2;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		c[i].push_back(pii(1, tmp));
		values.push_back({tmp, pii(i, 0)});
	}

	for (int i = 1; i < m; i++) {
		cin >> tmp >> tmp2;
		c[tmp-1].push_back(pii(i+1, tmp2));
		values.push_back({tmp2, pii(tmp-1, c[tmp-1].size()-1)});
	}

	sort(values.begin(), values.end());
	int counter = 0;
	int mapped = values[0].first;

	for (int i = 0; i < values.size(); i++) {
		if (values[i].first != mapped) {
			counter++;
		}

		c[values[i].second.first][values[i].second.second].second = counter;
	}

	for (int i = 0; i < m; i++) result[i] = i+1;

	spans.push_back(pii(0, m-1));
	span_count = 1;
	int lvl = 0;

	while (spans.begin() != spans.end() && lvl < n) {
		if (c[lvl].size() > 1) lsort(lvl);
		lvl++;
	}

	for (int i = 0; i < m; i++) cout << result[i] << ' ';

	cout << endl;

	return 0;
}