To improve her intelligence, ZJY is preparing to travel to a new world. The layout of cities in this world is like a tree. There is exactly one path between any two cities. Each city has a type of gem with a certain price. To earn the maximum profit, ZJY will choose to buy a gem in city A and then resell it in city B. Because ZJY often acts cute when buying gems, the price of gems in every city she passes through will increase. Let us calculate the maximum profit ZJY can earn after her trip. (For example, if the price of a gem in city $a$ is $v$, then the selling price for ZJY is also $v$.)

Input

The first line contains a positive integer $N$, representing the number of cities.

The next line contains $N$ positive integers, representing the initial price $p$ of the gem in each city. The initial price of each gem does not exceed $100$.

Starting from the third line, there are $N - 1$ lines, each containing two numbers $x$ and $y$, indicating that there is a path between city $x$ and city $y$. City numbering starts from $1$. The next line contains a positive integer $Q$, representing the number of queries.

The following $Q$ lines each contain three positive integers $a, b, v$, indicating that ZJY travels from $a$ to $b$, and the prices of gems in the cities along the path increase by $v$.

Output

For each query, output the maximum profit ZJY can obtain. If she makes a loss, output $0$.

Examples

Input 1

3
1 2 3
1 2
2 3
2
1 2 100
1 3 100

Output 1

1
1

Constraints

For $30\%$ of the data, $0 < N \le 100$, $0 < Q \le 10000$.

For $100\%$ of the data, $0 < N \le 50000$, $0 < Q \le 50000$.