Andy Jiang is studying data structures. One day, his friend Austin Zhu gave him a task on trees.
Austin provided a tree with vertices, numbered from to . Each vertex has a value .
For each query, Austin asked Andy to consider a path between two vertices and , and compute how many times a given value appears on that path.
Andy glanced at the problem and thought that this task was too easy for him.
Instead of just counting occurrences, Andy decided to challenge himself further. For each query, he wants to know how the frequency of compares to other values on the same path.
Formally, for each query :
Consider the simple path from to .
Let be the number of occurrences of value on this path.
Andy defines the rank of as .
That is, plus the number of distinct values that appear more frequently than on the path. Note that it is possible the value does not appear on the path, i.e. . In this case, you should return plus the number of distinct values on the path.
In some test cases, the queries are given in an encoded form as described below.
Help Andy compute the rank of for each query.
输入格式
The first line contains positive integers , , and (, ).
The second line contains integers ().
The next lines each contain two integers (), representing the -th edge.
Each of the next lines contains integers (, ), describing the -th query.
Let . For each query , the actual parameters are defined as:
After computing the answer to the -th query, set
It may also be useful to note that “mod” corresponds to the operator in most programming languages, indicating the remainder after division. For example, and .
输出格式
For each query, output the answer to the query on a new line.
