Convenience Value of the Shop

In the world of Gensokyo, there are n locations numbered from 1 to n that form a tree (i.e. a connected acyclic graph) with n-1 weighted edges. Every location i has a resident monster with age x_i. The tree has a special property: the degree of any node is at most 3.

You are given a proposal to open a shop at a location u, targeting monsters whose ages fall within the interval \([L,R]\). The convenience value of this proposal is defined as the sum of the distances from u to every location v such that the age x_v satisfies \(L \le x_v \le R\). The distance between two nodes is defined as the sum of the weights on the unique simple path between them.

Your task is to answer several such queries. For each query, given the location u and the age range \([L,R]\), compute the corresponding convenience value.

Input Format: The first integer is n (the number of nodes). The next line contains n integers, where the i-th integer denotes x_i, the age of the monster at node i. The following n-1 lines each contain three integers u v w representing an edge between nodes u and v with weight w. Then an integer q is given, representing the number of queries. Each of the next q lines contains three integers u L R representing a query.

Output Format: For each query, output a single line containing the convenience value as defined above.

Note: It is guaranteed that the tree structure has maximum degree at most 3. You may assume that \(n\) and \(q\) are small enough such that a solution with a DFS (or BFS) on the tree for each query is efficient.

inputFormat

The input is given in the following format:

n
x1 x2 x3 ... xn
u1 v1 w1
u2 v2 w2
... (n-1 lines)
q
u1 L1 R1
u2 L2 R2
... (q lines)

Where:

• n is the number of nodes.
• x_i (for 1 ≤ i ≤ n) represents the age at node i.
• Each of the next n-1 lines contains an edge represented by two node indices and a weight.
• q is the number of queries.
• Each query consists of a node u and two integers L and R specifying the age interval.

outputFormat

For each query, output the convenience value — the sum of distances from the query node u to every node whose age is in the interval \([L,R]\).

sample

5
10 20 30 40 50
1 2 1
1 3 2
3 4 3
3 5 4
3
1 10 30
3 20 50
4 15 35

3
10
9