There exits an edge-weighted directed tree rooted at node \(1 \), where edges are directed from child towards the parent, and each edge has a positive weight. Let's call this tree \(\text{Tree}_1\). 

There exists another tree, \(\text{Tree}_2\) which is constructed from \(\text{Tree}_1\) as: Copy entire \(\text{Tree}_1\) and double each of it's edge value (Edges remain directed in \(\text{Tree}_2\) as well). 

There also exits an undirected weighted edge, with weight \(w[v]\) between node \(v\) of \(\text{Tree}_1\) and node \(v\) of \(\text{Tree}_2\), for all \(1\leq v\leq n\) (where \(n\) is the number of nodes in the trees). 

You will be given \(q\) queries of the form \(u\), \(v\) where \(v\) will be ancestor of \(u\). You will have to find the length of the shortest path from \(u\) to \(v\) in \(\text{Tree}_2\) (mean you've to start in node \(u\) in \(\text{Tree}_2\) and reach node \(v\) in \(\text{Tree}_2\)).

Input Format

• The tree is given in input as undirected tree, rooted at \(1\).
• First line contains a single integer \(n\) - no. of nodes in the tree.
• Each of the next \(n-1\) lines contains 3 space separated intergers -  \(u \space v \space x\) . Indicating there is an edge between \(u\) and \(v\) with weight \(x\) in \(\text{Tree}_1\).
• Next line contains \(n\) space-separated integers - \(w[v]\)  for each node from \(1\) to \(n\).
• Next line contains a single integer - \(q\) - no. of queries
• Each of the next \(q\) lines contains \(2\) space seperated integers - \(u\) \(v\). It is guranteed that \(v\) will be an ancestor of  \(u\).

Output Format

For each query print a single integer in a separate line which is the answer to the query.

Constraints

\(1 \leq n, q \leq 3 \cdot 10^5 \\ 1 \leq u, v \leq n \\ 1 \leq w[v], x \leq 10^9\)