Path Sum of Depth Powers in a Tree

You are given a rooted tree with n nodes. The tree is defined such that the root is node 1. The depth of a node is the number of edges on the unique path from the root to that node (the root has depth 0).

You will be given multiple queries. In each query you are given three integers u, v and k. For each query, consider the unique path from node u to node v. Your task is to compute the sum of the kth power of the depth of each node on that path. Formally, if the path is u = v1, v2, ..., vm = v, you need to compute:

Note: When k = 0, each term is 1, so the answer is simply the number of nodes in the path.

The input guarantees that the tree is given in a format where for every node i (from 2 to n), its parent is provided. Use node 1 as the tree root.

inputFormat

The input consists of multiple lines:

1. The first line contains an integer n — the number of nodes in the tree.
2. The second line contains n-1 space-separated integers. The i-th integer (for i = 2, 3, ..., n) represents the parent of node i.
3. The third line contains an integer q — the number of queries.
4. Each of the next q lines contains three space-separated integers: u, v and k, describing a query.

outputFormat

For each query, print a single integer — the sum over the path from u to v of (depth(v))^k (where depth(v) is the depth of node v). Output each answer on a new line.

sample

5
1 1 2 2
3
4 5 2
2 3 1
4 3 0

9
2
4