The Union of Wizard Bankers (UWB) runs a network of banks in which they store gold coins, connected by portals. Because portal maintenance is expensive, they use the minimal number of portals such that each bank is reachable from any other (in other words, they form a tree). This can be used to send coins from one bank to another, via the portal that connects them, but sending a coin through a portal requires fuel: a crystal of tympestyne, a rare mineral.

The union wishes to be prepared for anything: if an emergency arises, they plan to move all coins to a single bank, so that they can unite in its defence. Since tympestyne is expensive, they wish to pick a bank that minimises the number of crystals required for this. As these bankers are wizards, not programmers, they cannot quickly figure out which bank that should be. Help them to find the one that would be cheapest to transfer resources to at any given time!

Input format

The first line of standard input contains \(N\), the number of banks.

The following \(N-1\) lines each contain two integers \(x_i\) and \(y_i\), between \(1\) and \(N\), meaning that a portal connects banks \(x_i\) and \(y_i\).

The following line contains \(N\) integers: the initial number of gold coins in each of the banks.

The next line contains \(Q\), the number of queries. \(Q\) queries follow, one per line. Each query consists of two numbers \(z_i\) and \(b_i\), meaning that \(z_i\) coins were deposited to the bank \(b_i\).

Output format

Your program should print \(Q+1\) numbers. The first is the index of the bank that the UWB should move all coins to (with a minimal cost) if there is an emergency before the first query. In the next \(Q\) lines, you should print the optimal choice after some of the deposits described by the queries happened: in the \(i\)-th, print the best bank after the first \(i\) deposits.

If there are multiple banks that minimise the cost, your program should output the one with the lowest index.

Sample 1

Input

5
1 2
2 3
3 4
4 5
1 1 1 1 1
2
8 5
6 2

Output

3
5
4

Explanation

• Before the first deposit, bank \(3\) is optimal: we would need \(6\) crystals to move all coins there.
• After the first deposit, bank \(5\) becomes optimal, and we would need \(10\) crystals.
• After the second deposit, bank \(4\) becomes optimal, and the transfer would cost \(15\) crystals.

Sample 2

Input

4
1 2
1 3
1 4
1 1 1 100
0

Output

4

Explanation

The last bank contains by far the most coins, so it is clear that choosing any other location would be more expensive.

Constraints

• \(1 \leq N,Q \leq 200 000\).
• The initial number of coins in each bank is at least \(1\).

Testcases are split into five non-overlapping groups:

• In tests worth 15 points: \(N \leq 1000, Q=0\).
• In tests worth 15 points: \(Q=0\).
• In tests worth 20 points: Each bank is connected to at most two other banks.
• In tests worth 20 points: The graph of banks is a complete binary tree.
• In tests worth 30 points: No additional constraints.