Optimal Profit from Three Lectures

M country has n cities numbered 1, 2, …, n and n - 1 bidirectional roads, forming a tree (i.e. the cities are connected). The i-th road connects city \(u_i\) and city \(v_i\) with a toll of \(w_i\). When you hold a lecture in city i, you earn an income of \(c_i\). You are a speaker who gives three lectures each day. On a given day:

• The first lecture must be held in city \(x\).
• The third lecture must be held in city \(y\).
• You may choose any city \(z\) for the second lecture (and it is allowed to hold more than one lecture in the same city in one day).

When traveling, you must pay the toll for every road you pass. In particular, if a road is used more than once in the journey from \(x \to z\) and then \(z \to y\), you pay its toll each time it is passed. The total revenue for the day is the sum \(c_x + c_y + c_z\) and the total cost is the toll sum along the path from \(x \to z\) and from \(z \to y\). Note that the answer (profit) may be negative.

Your task is, for each day, given \(x\) and \(y\) (for the first and third lectures, respectively), to choose an optimal city \(z\) for the second lecture so that the profit, defined as

[ \text{Profit} = c_x + c_y + c_z - \Big( d(x, z) + d(z, y) \Big), ]

is maximized. Compute and output the maximum profit for each day.

inputFormat

The input is given as follows:

1. An integer \(n\) denoting the number of cities. \(n \ge 2\).
2. A line with \(n\) integers \(c_1, c_2, \dots, c_n\) where \(c_i\) is the revenue from a lecture in city \(i\).
3. \(n - 1\) lines each containing three integers \(u_i\), \(v_i\), and \(w_i\) representing a road between cities \(u_i\) and \(v_i\) with toll \(w_i\). It is guaranteed that the cities form a tree.
4. An integer \(q\) representing the number of days (queries).
5. \(q\) lines each containing two integers \(x_i\) and \(y_i\), indicating that the first lecture is in city \(x_i\) and the third lecture is in city \(y_i\) for that day.

All values are separated by whitespace.

outputFormat

For each query, output a single line containing the maximum profit achievable on that day.

sample

4
3 2 5 1
1 2 4
2 3 3
2 4 2
3
1 3
4 3
1 4

6
6
1