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
#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <climits>
#include <numeric>

struct Change {
	int begin, val, right;
};

std::vector<std::vector<Change>> columns;
std::vector<Change*> pairsSorted;
std::vector<Change> result;

int getBegin(const std::vector<Change>& vec, size_t i) {
	return (i < vec.size() ? vec[i].begin : INT_MAX);
}

std::vector<Change> merge(std::vector<Change>& left, std::vector<Change>& right) {
	// Aggregate pairs

	Change elem{0, left[0].val, right[0].val};
	std::vector<Change> pairs;
	pairs.push_back(elem);

	size_t l = 0, r = 0;

	while (l+1 < left.size() || r+1 < right.size()) {
		if (getBegin(left, l+1) < getBegin(right, r+1)) {
			elem.begin = left[++l].begin;
			elem.val = left[l].val;
		} else {
			elem.begin = right[++r].begin;
			elem.right = right[r].val;
		}

		pairs.push_back(elem);
	}

	// Sort pairs

	pairsSorted.clear();
	for (auto& p : pairs) {
		pairsSorted.push_back(&p);
	}

	sort(pairsSorted.begin(), pairsSorted.end(), [](Change* l, Change* r)->bool {
		return l->val < r->val || (l->val == r->val && l->right < r->right);
	});

	// Enumerate

	int val1 = -1, val2 = -1, num = 0;

	for (auto cur : pairsSorted) {
		num += (cur->val != val1 || cur->right != val2 ? 1 : 0);
		val1 = cur->val;
		val2 = cur->right;
		cur->val = num;
	}
	return pairs;
}

std::vector<Change> solve(int begin, int end) {
	if (begin+1 == end) {
		return columns[begin];
	}

	int mid = (begin+end) / 2;
	auto left = solve(begin, mid), right = solve(mid, end);
	return merge(left, right);
}

int main() {
	std::ios::sync_with_stdio(false); std::cin.tie(0);

	int nCols, nLines; std::cin >> nCols >> nLines;
	columns.resize(nCols);

	for (auto& col : columns) {
		int val; std::cin >> val;
		col.push_back({ 0, val, 0 });
	}

	for (int line = 1; line < nLines; line++) {
		int col, val; std::cin >> col >> val;
		columns[col-1].push_back({ line, val, 0 });
	}

	result = solve(0, nCols);

	// Print

	std::vector<int> order(nLines);
	std::iota(order.begin(), order.end(), 0);

	std::stable_sort(order.begin(), order.end(), [](int l, int r)->bool {
		return result[l].val < result[r].val;
	});

	for (int x : order) {
		std::cout << x+1 << " ";
	}
	std::cout << std::endl;
	return 0;
}