Boss Bo

Problem Description

There is a tree with $N$ nodes, whose root is 1. There are $Q$ queries for you,for each query,we will give $K$ numbers,which are $A_1,A_2,\dots,A_K$. For every node $x\in[1,N]$ in the tree,we assume it's good if there is not a node $y\in A$,such that $y$ is the ancient of $x$ or $y=x$ And we will give two numbers $T , P$ to show the property of each query. 1.when $T=1$,you should output the sum of the distance between every good node and $P$. 2.when $T=2$,you should output the minimum distance between every good node and $P$. 3.when $T=3$,you should output the maximum distance between every good node and $P$. Let the distance between nodes in the tree be the shortest path between these two nodes.And we assume the length of each edge is 1. Specially,the distance between two same nodes is 0. For each query,if there is no nodes that is good,just output -1.

Input

There are several test cases. For each test case,the first line contains two numbers $N$ and $Q$. For the following $N-1$ lines,each line contains two numbers $u$ and $v$,indicating there is a edge between $u$ and $v$ in tree. For the following $Q$ lines,each line contains some numbers,which are $K,P',T,A_1,A_2,\dots,A_K$ in order. Let the answer of last query be $lastans$,then $P=(P' + lastAns)~\mod{N} + 1$. If the answer of last query is -1 or it's the first query,then $lastans=0$. Let the number of test cases be $T$,we guarantee $T=30$. $80\%$ test cases satisfy $N,K,Q \le 10000$ ,$\sum{K} \le 20000$. $100\%$ test cases satisfy ~$P, N,K \le 50000$,$Q \le 100000$,$\sum{K} \le 200000$.

Output

You should output Q lines in total,each line contains a number indicating the answer of each query.

Sample Input

6 5
1 3
2 1
4 2
6 4
5 6
3 5 3
3 3 3
3 4 3
4 5 1
3 3 1
1 5 6
3 5 2
3 4 2
3 3 3
6 5 3

Sample Output

3
-1
-1
3
2

Author

绍兴一中

Source

2016 Multi-University Training Contest 3