LCA and Queries

Time limit5sMemory limit1536 MB

Summary

Given a rooted tree and several queries, each listing K vertices, compute the sum of the LCA levels over all pairs of those vertices.

Problem

For a tree $T$ with $N$ vertices, write a program that processes the following query.

$K \ V_1 \ V_2 \ \cdots \ V_K$ : For every pair $(i, j)$ with $1 \leq i < j \leq K$ , print the sum of the levels of the LCA of vertex $V_i$ and vertex $V_j$ .

The root of $T$ is vertex 1. The root has level 0, and every other vertex has level (level of its parent) + 1.

The LCA of two vertices $u$ and $v$ is the closest common ancestor of $u$ and $v$ (the lowest common ancestor).

The first line contains the number of vertices $N$ and the number of queries $Q$ .

The second line contains the parent vertices $P_2, P_3, \cdots, P_N$ of vertices $2, 3, \cdots, N$ .

Each of the next $Q$ lines contains a query $K \ V_1 \ V_2 \ \cdots \ V_K$ , with the values separated by spaces.

For each query, print the result on its own line.

Example 1

Input

16 4
1 2 3 4 3 1 7 8 9 7 11 12 1 14 15
2 4 5
2 10 13
3 4 6 16
4 4 10 6 13

Expected output