Problem Description

To enhance her intelligence, ZJY plans to travel to a new world. The cities in this world are laid out like a tree, with only one path connecting any two cities.

Each city has a gemstone with a certain price. ZJY aims to maximize her profit by buying from city A and selling in city B.

Due to ZJY's charm when buying gems, the price of gems in any city she passes through will increase. Let's calculate the maximum profit ZJY can make after her trip. (If the gem price in city A is $v$, ZJY's selling price is also $v$.)

Input Format

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

The next line contains $n$ positive integers representing the initial prices $p$ of gems in each city, with each initial price not exceeding $100$.

The following $n-1$ lines each contain 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 city $a$ to city $b$, and the gem price in each city increases by $v$.

Output Format

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

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
1

Input Sample #2

5
1 2 3 4 5
1 2
1 3
2 4
4 5
6
1 5 50
2 4 500
3 4 5000
3 5 50000
1 3 500000
2 3 5000000

Output Sample #2

4
2
551
551
0
499499

Notes

Data Size and Constraints

• For $30\%$ of the data, $n \le 100$ and $q \le 10^4$.
• For $100\%$ of the data, $1 \le n, q \le 5 \times 10^4$, and the gem price in any city at any time does not exceed $10^9$.

见题面 Input 部分

见题面 Output 部分