Victoria has a tree, , consisting of nodes numbered from to . Each edge from node to in tree has an integer weight, .
Let's define the cost, , of a path from some node to some other node as the maximum weight () for any edge in the unique path from node to node .
Victoria wants your help processing queries on tree , where each query contains integers, and , such that . For each query, she wants to print the number of different paths in that have a cost, , in the inclusive range .
It should be noted that path from some node to some other node is considered same as path from node to i.e is same as .
Input Format
The first line contains space-separated integers, (the number of nodes) and (the number of queries), respectively.
Each of the subsequent lines contain space-separated integers, , , and , respectively, describing a bidirectional road between nodes and which has weight .
The subsequent lines each contain space-separated integers denoting and .
Constraints
Scoring
- for of the test data.
- for of the test data.
Output Format
For each of the queries, print the number of paths in having cost in the inclusive range on a new line.
Sample Input
5 5 1 2 3 1 4 2 2 5 6 3 4 1 1 1 1 2 2 3 2 5 1 6 Sample Output
1 3 5 5 10 Explanation
:
:
:
:
...etc.