Path Statistics
You are given a tree with nodes, that is, an acyclic connected graph, where each node is assigned a value .
You must answer queries in the form u v k. For each query, find and print the most frequent value on the path between and . If two values appear the same number of times, for tie-breaking, the smaller number is considered less frequent than, the bigger one.
Input Format
The first line contains two space-separated integers describing the respective values of and .
The second line contains space-separated integers describing the respective values of .
Each of the subsequent lines contains two space-separated integers, and , describing an edge between nodes and .
Each of the subsequent lines contains three space-separated integers, , and , describing a query.
Constraints
Subtasks
- For of the total points,
Output Format
For each query, print a single line containing a single integer denoting the most frequent value on the path between and .
Sample Input 0
6 4
1 1 3 2 4 2
1 4
4 5
6 2
3 6
4 2
1 2 1
1 2 2
1 3 1
1 3 3
Sample Output 0
1
2
2
3
Explanation 0
For the first and second queries, the numbers that appear on the path are: . The most frequent number is , and the second one is .
For the third and fourth queries, the path is composed by . Since both and appear twice on the path, and according to the problem statement, being smalled is considered less frequent than , the answer for the query 1 3 1 is , because is the most frequent number. The second most frequent number is (only because it is smaller than ), and the third one is , thus the answer for the last query is .