You are given a Tree with N nodes rooted at 1. You are also given an array of M elements. Now, you are given Q queries. Each query contains four numbers - a,b,c,d. Here a & b denote the nodes in tree whereas c & d denote the index in the array.

You can atmost replace one edge weight in the path of a & b from the values present in array in index [c,d]. Note that each query is independent of each other so the replacement of edge weight in one query will be reversed back to it's original after each query.

Now, your goal should be to maximize F(a,b). F(a,b) = maximum difference between any pair of edge weight that comes between the path of node a to b.

Note:- In Query a can be equal to b ( a=b ), for that case print 0. Also when there is exactly 1 edge between the path from a to b, print 0.

INPUT

First Line - N

N-1 Lines Follows- each line contains 3 numbers - u,v,w denoting an edge between u & v with weight w.

Then Line contains M

M elements denoting the values in the array.

Then Q.

Q lines each followed by 4 numbers - a,b,c,d.

OUTPUT

For Each query print F(a,b).

CONSTRAINTS

1<=N,M,Q<=100000

1<=a,b<=N

1<=c,d<=M