Taylor loves trees, and this new challenge has him stumped!
Consider a tree, , consisting of nodes. Each node is numbered from to , and each node has an integer, , attached to it.
A query on tree takes the form w x y z. To process a query, you must print the count of ordered pairs of integers such that the following four conditions are all satisfied:
- the path from node to node .
- path from node to node .
Given and queries, process each query in order, printing the pair count for each query on a new line.
Input Format
The first line contains two space-separated integers describing the respective values of (the number of nodes) and (the number of queries).
The second line contains space-separated integers describing the respective values of each node (i.e., ).
Each of the subsequent lines contains two space-separated integers, and , defining a bidirectional edge between nodes and .
Each of the subsequent lines contains a w x y z query, defined above.
Constraints
Scoring for this problem is Binary, that means you have to pass all the test cases to get a positive score.
Output Format
For each query, print the count of ordered pairs of integers satisfying the four given conditions on a new line.
Sample Input
10 5
10 2 3 5 10 5 3 6 2 1
1 2
1 3
3 4
3 5
3 6
4 7
5 8
7 9
2 10
8 5 2 10
3 8 4 9
1 9 5 9
4 6 4 6
5 8 5 8
Sample Output
0
1
3
2
0
Explanation
We perform queries on the following tree:
- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . No such pair exists, so we print .
- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . One such pair, , exists, so we print .
- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . Three such pairs, , , and exist, so we print .
- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . Two such pairs, and , exist, so we print .
- Find the number of valid ordered pairs where is in the path from node to node and is in the path from node to node . No such pair exists, so we print .