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
#include <cstdio>
#include <algorithm>
#include <map>

const int U = 1<<19;
const int UU = 19;
const int M = 501013;
const int MM = 11091013;

int w[U], p[M], ww;

int ls[MM], ps[MM], o[MM];

std::map<long long, int> ma;

int tworz(int v, int vl, int vp) {
	//printf("stworz mi %d %d %d\n",v,vl,vp);
	if (!v) {
		int& x = ma[((long long)vl) * MM + vp];
		//printf("%d\n", x);
		if (!x) x = ww++;
		v = x;
	} else {
		ma[((long long)vl) * MM + vp] = v;
	}
	if (vl > 0) { 
		o[vl] = o[vp] = v;
	}
	ls[v] = vl;
	ps[v] = vp;
	//printf("%d :: %d %d\n", v, vl, vp);
	return v;
}

bool comp(int a, int b) {
	if (p[a] == p[b]) return a < b;
	//printf("por %d %d :: \n",a,b);
	a = p[a], b = p[b];
	while (ls[a] > 0) {
		//printf("%d %d :: %c\n", a, b, ls[a] == ls[b] ? 'P' : 'L');
		if (ls[a] == ls[b]) a = ps[a], b = ps[b];
		else a = ls[a], b = ls[b];
	}
	//printf("%d %d :: %d %d\n", ls[a], ls[b], ps[a], ps[b]);
	return ps[a] < ps[b];
}

int main() {
	int n,m;
	scanf("%d %d",&n,&m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &w[i+1]);
	}
	for (int i = 0; i < U; i++) {
		tworz(i+U, -i, w[i]);
		w[i] = i+U;
	}
	for (int i = U-1; i >= 1; i--) {
		tworz(i, i+i, i+i+1);
	}
	p[1] = 1;
	ww = U+U;
	for(int i = 2; i <= m; i++) {
		int pi, xi;
		scanf("%d %d",&pi,&xi);
		int nowy = tworz(0, -pi, xi);
		int pop = w[pi];
		w[pi] = nowy;
		for (int j = 0; j < UU; j++) {
			//printf("pop=%d nowy=%d\n",pop,nowy);
		  int ll = ls[o[pop]];
			int pp = ps[o[pop]];
			if (ll == pop) ll = nowy;
			else pp = nowy;
			pop = o[pop];
			nowy = tworz(0, ll, pp);
		}
		p[i] = nowy;
//		if (i % 1000 == 0) printf(" ==== %d %d ... %d\n", i, nowy, ww);		
		
	}
	for (int i = 1; i <= m; i++) w[i] = i;
	std::sort(w+1, w+m+1, comp);
	for(int i = 1; i <= m; i++) printf("%d ", w[i]);
	printf("\n");
	return 0;
}