Geografia dos Rios

#27

Made by: Bernardo Amorim e Bruno Monteiro

1024MB

Ao estudar a geografia dos rios do mundo, você se pergunta: quando dois rios se unem, quem escolhe qual vai ser o nome do rio a partir dessa junção? De fato, a resposta é simples: com a união de dois rios, o nome passa a ser o nome daquele que tinha maior volume de água. Dado que todos os rios eventualmente se unem e desaguam no mar, um problema interessante é calcular, dado o nome de cada nascente, o nome do rio final que desagua no mar.

Formalmente, são dadas $N$ nascentes de rios. Para cada nascente, você tem uma quantidade de litros de água li que nasce dela. Além disso, pares de rios se encontram (como uma árvore binária), até todos se juntarem e desaguarem no mar. Quando dois rios se encontram, a quantidade de litros de água é somada, e o nome do rio passa a ser o nome do rio que tinha mais água, ou, em caso de empate, o de menor ı́ndice. O nome inicial de cada nascente é seu ı́ndice.

O que você quer saber é o nome do rio que por fim deságua no mar. Porém, estamos em época de chuvas! Você precisa processar $Q$ operações. Em cada uma delas, uma chuva aconteceu que causa com que em uma nascente $n_i$ agora nasce $q_i$ litros a mais de água (e isso será mantido para as operações futuras). Depois de cada operação, calcule o nome do rio que desagua no mar.

Input

A primeira linha contém um inteiro $N$ $(1 ≤ N ≤ 10^5 )$: o número de nascentes.

A segunda linha contém $N$ inteiros $l_i$ $(1 ≤ l_i ≤ 10^9 )$: o número de litros de água que nascem nanascente $i$.

As $N − 1$ linhas seguintes descrevem como os rios se unem. Na i-ésima delas, dois inteiros $a_i$ , $b_i$ $(1 ≤ a_i , b_i < N + i)$ indicam que os rios $a_i$ e $b_i$ se unem para formar o rio $N + i$ (cujo volume de água será a soma dos volumes de $a_i$ e $b_i$ , e nome será o nome do que tiver mais volume de água). É garantido que os valores $a_i$ e $b_i$ são válidos, isto é, $a_i \neq b_i$ e nenhum deles já foi unido previamente na entrada.

A próxima linha contém um inteiro $Q$ $(1 ≤ Q ≤ 10^5 )$, o número de operações. Seguem $Q$ linhas com as operações: a i-ésima linha contém dois inteiros $n_i$ e $q_i$ $(1 ≤ n_i ≤ N)$ e $(1 ≤ q_i ≤ 10^9 )$, significando que na nascente representada pelo ponto $n_i$ agora nasce $q_i$ litros a mais de água.

Output

Imprima, na primeira linha, o nome do rio que inicialmente desagua no mar. Em seguida, imprima $Q$ linhas: após cada operação, o nome do rio que desagua no mar.

Input Example

Output Example

2
3
2

3
2
2