Alice is a merchant in the world. Layout of this world is a tree. There is only one path between any two cities. Each city has a unique gem with a starting price. Alice will choose to buy from city A and then sell in City B. As Alice passes through each of the cities, the city’s gem prices will rise. Calculate the maximum profit that Alice can earn after traveling. If a profit is not possible, Alice will stay at home. Note that the price of all gems (regardless of which one or type) in a given city is always the same. Input A number of of inputs (≤ 20) described as follows. Input start with N, the number of cities (0 < N ≤ 50000). The next N lines has the initial price P in each city (0 < P ≤ 1000). This is followed by N − 1 line consecutively, with two numbers x and y between 1 and N on each line, specifying there is a road between cities x and y. The next line is an integer Q, the number of inquiries (0 < Q ≤ 50000). Then Q lines, each line input three positive integer a, b, v, which means Alice travels from a to b, and the price of gem rises by v (0 < v ≤ 1000000000, 1 ≤ a,b ≤ N) for each city on the shortest path from a to b. Note that price increases from a query will persist for future queries on the same input set. Output Output for each query, Alice’s maximum profit possible. Note, return ‘0’, if Alice stays at home (no profit is possible). Sample Input 3 123 12 23 2 1 2 100 1 3 100 Sample Output 1 1