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$