You are given a tree with nodes and edges. Each node of the tree is assigned a color . Let be the array of colors encountered while traversing from node to node in the tree in the order.
Let represent the number of inversions in the array .
You need to compute for different queries.
Input format
Output format
For each query output the answer in a new line representing the value .
Constraints