강의 지리

세계의 강을 지리적으로 공부하다 보면 이런 의문이 생길 수 있다. 두 강이 합쳐질 때, 합쳐진 강의 이름은 누가 정하는가? 답은 간단하다. 두 강이 합쳐지면 물의 양이 더 많은 강의 이름이 새 강의 이름이 된다. 모든 강은 결국 합쳐져서 바다로 흘러 들어간다. 따라서 각 수원의 이름이 주어졌을 때, 바다로 흘러 들어가는 최종 강의 이름을 구하는 것이 문제다.

형식적으로 말하면, $N$개의 수원이 주어진다. 수원 $i$에서는 $l_i$리터의 물이 나온다. 강들은 둘씩 만나며(이진 트리처럼), 결국 모두 합쳐져 바다로 흘러 들어간다. 두 강이 만나면 물의 양이 더해지고, 새 강은 물이 더 많은 강의 이름을 받는다. 양이 같으면 번호가 작은 강의 이름을 쓴다. 각 수원의 처음 이름은 그 번호이다.

결국 바다로 흘러 들어가는 강의 이름을 구해야 한다. 그런데 지금은 우기다! $Q$번의 연산을 처리해야 한다. 각 연산에서 비가 내려 수원 $n_i$에 $q_i$리터의 물이 추가되며, 이 효과는 이후 연산에도 그대로 남는다. 매 연산 후에 바다로 흘러 들어가는 강의 이름을 계산하라.

첫 번째 줄에 정수 $N$ ($1 \le N \le 10^5$)이 주어진다. 이는 수원의 개수이다.

두 번째 줄에는 $N$개의 정수 $l_i$ ($1 \le l_i \le 10^9$)가 주어진다. 이는 수원 $i$에서 나오는 물의 양(리터)이다.

이어지는 $N-1$개의 줄은 강이 어떻게 합쳐지는지를 설명한다. 그중 $i$번째 줄에는 두 정수 $a_i$, $b_i$ ($1 \le a_i, b_i < N+i$)가 주어지며, 강 $a_i$와 강 $b_i$가 합쳐져 강 $N+i$가 된다는 뜻이다. 새 강의 물의 양은 $a_i$와 $b_i$의 물의 양을 더한 값이고, 이름은 물의 양이 가장 많은 강의 이름이다. 입력 값은 유효하다고 보장되며, $a_i \ne b_i$이고 두 강 모두 입력에서 이전에 합쳐진 적이 없다.

다음 줄에는 연산의 수 $Q$ ($1 \le Q \le 10^5$)가 주어진다.

이후 $Q$개의 줄에 연산이 주어진다. $i$번째 줄에는 두 정수 $n_i$, $q_i$ ($1 \le n_i \le N$, $1 \le q_i \le 10^9$)가 주어지며, 이는 수원 $n_i$가 이제 $q_i$리터 더 많은 물을 낸다는 뜻이다. 이 변화는 이후 연산에도 유지된다.

첫 줄에 처음에 바다로 흘러 들어가는 강의 이름을 출력한다. 그다음 $Q$개의 줄을 출력한다. 각 연산 후에 바다로 흘러 들어가는 강의 이름을 출력한다.