Problem D. Tree in the Typhoon

Time limit: 5 seconds

Problem

Typhoon Koppu hit Hong Kong in the first week of the semester and a half day of class was cancelled. When the typhoon is finally gone, Kitty discovers that many trees near the campus was broken. Some branches were cut and become leafless. Kitty is very much bothered by this as she loves trees a lot. As Kitty wanders on the campus, she becomes immersed in a problem...

Every tree on the campus can be represented as a rooted tree in the sense of graph theory, i.e. the tree grows from a single root, then branches, and eventually has leaves as the endpoints. Given an unweighted rooted tree, the depth of each node is the distance of the node from the root.

With the tree structure known, we have Q independent queries of possible damage of the typhoon. Each query is in the form of an integer d, meaning that all nodes (i.e. leaves, intermediate branch-points in the tree or the root) with depth >= d are cut. For each query, you are find out the damage to the tree. Specifically, you need to output the number of remaining nodes, the number of remaining leaves and the number of leafless endpoints after the damage. Each query is independent of each other.

For example, the following show a tree of height 3 with three leaves at the beginning:

Suppose the typhoon cut the tree at depth 1, then all nodes except the root is cut. The remaining number of nodes is therefore 1, with no leaves, and one leafless endpoint (since the root is now an endpoint).

On the other hand, if the typhoon has been less severe and cut the tree at depth 2, then only the leaf at depth 2 is cut. Thus we have 4 nodes remaining, 2 being leaves. There is also 1 leafless endpoint because the rightmost node in Depth 1 is now an endpoint but it is leafless originally.

Input

The first line of the input contains an integer T, which is the number of test cases. Then the input of the T test cases follows. For each test case, the first line contains N, the number of nodes in the tree, and Q, the number of queries. You can assume that N <=100,000 . The nodes are labelled 0 to N-1, with 0 always being the root. Then the next line contains N-1 integers, the ith one giving the parent of the node i. The next line contains Q integers, each representing a query.

Output

For the ith test case, first output "Case i:". Then output one line for each query, with the three integers, i.e. the number of remaining nodes, the number of remaining leaves and the number of leafless endpoints, separated by single spaces.

Sample Input

1
5 2
0 0 0 3
1 2

Sample Output

Case 1:
1 0 1
4 2 1

Author

Kelly Choi