# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## So Much Difference

Difference starts with a ’D’. This is the root of all dissimilarities and arguments and fights. Figuring out differences is just like figuring out your life. Sometimes they confuse you but in the end it is all worth it. If you can’t find out the difference between things, or solve the difference between people, your life is as meaningless as you are. But before you can solve the difference between things you must find it out. That’s why you have made a function that can figure out the difference between everything.

You are given a Tree. And some paths on that tree, you need to use your function to figure out the difference between those paths.

```
function Distance(x1, y1, x2, y2)
Array1 = []
Array2 = []
For A1 = nodes on the unique path from x1 to y1
Array1.push(V[A1])
end For
For A2 = nodes on the unique path from x2 to y2
Array2.push(V[A2])
end For
NewArray1 = sort the elements inside Array1
NewArray2 = sort the elements inside Array2
len1 = element count in Array1
len2 = element count in Array2
mid1 = ceiling(len1 / 2)
mid2 = ceiling(len2 / 2)
maxFreq = 0
For P = elements in Array1
cnt = 0
For Q = elements in Array1
if P equals Q
cnt = cnt + 1
end if
end For
maxFreq = Maximum(maxFreq, cnt)
end For
//|A| denotes the absolute value of A
difference = |NewArray1[mid1] - NewArray2[mid2]|
return (maxFreq * difference)
end function
```

**Note: All the Array index starts from 1**

### Input

The first line contains an integer **N** number of nodes in the tree.

Then there will be a single line containing **N** integers **V[1], V[2], V[3], … V[N]**. **V[i]** is the value on the **i ^{th}** node.
Following

**(N - 1)**lines will contain two integers

**u**and

**v**, means there is a edge from

**u**to

**v**. Edges are bidirectional.

Then there will be Q queries. Each line will contain four integers **x1**, **y1**, **x2**, **y2**.

- 1 ≤ N ≤ 10
^{5} - 1 ≤ u, v, x1, y1, x2, y2 ≤ N
- 1 ≤ Q ≤ 10
^{5} - -10
^{8}≤ V[i] ≤ 10^{8}

### Output

For each query output the answer of the Distance function in a single line. For better understanding check the samples.

### Samples

Input | Output |
---|---|

8 1 2 3 4 5 6 7 8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 5 1 2 1 7 2 8 4 8 1 5 5 8 1 8 2 5 8 8 3 7 | 3 1 3 1 3 |

Note: All the Array index starts from 1.

#### IamHot

→