题目描述

小 C 和小 F 同学认为跑步非常非常有趣，于是决定制作一款叫做《天天爱跑步plus》的游戏。《天天爱跑步plus》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含 $n$ 个结点和 $n-1$ 条带权边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达，两个节点间的距离定义为树上路径的边权和。树上结点编号为从 $1$ 到 $n$ 的连续正整数。

游戏将会进行 $m$ 天，第 $i$ 个节点每天有 $cnt_i$ 个玩家上线，每天将会有若干个打卡点，所有玩家上线后会向距离最近的打卡点跑去。作为小 C 和小 F 的好基♂友 TLC ，你需要实时统计出每一天所有玩家跑步的距离和，即本题强制在线。

输入格式

第一行一个整数 $T$ ，代表测试点编号 (样例编号为 $0$ ) 。

第二行有两个整数 $n,m$ ，代表树的结点数和游戏进行的天数。

接下来 $n-1$ 行每行有三个整数 $x,y,w$ ，代表结点 $x$ 与结点 $y$ 之间有一条边权为 $w$ 的边。

接下来一行有 $n$ 个整数 $cnt_i$ ，代表第 $i$ 个结点每天上线的玩家数。

接下来 $m$ 行第 $i$ 行先有一个整数 $num_i$ ，代表第 $i$ 天开放的打卡点个数，随后有 $num_i$ 个整数 $t_{i,j}'$ 代表加密后的开放的打卡点编号。

每天给出的打卡点编号经过了加密，实际的打卡点编号 $t_{i,j}=t_{i,j}'\oplus (ans_{i-1}\mod n)$ ，其中 $ans_{i-1}$ 代表第 $i-1$ 天的答案(初始时 $ans_0=0$ )

输出格式

输出 $m$ 行，每行一个整数 $ans_i$ ，代表第 $i$ 天的答案。

输入输出样例

输入 #1

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

输出 #1

10
5
14
13
10

输入 #2/输出 #2

见下发样例的 sample_runplus2.in/sample_runplus2.out，该样例满足测试点 $1$ 的限制。

输入 #3/输出 #3

见下发样例的 sample_runplus3.in/sample_runplus3.out，该样例满足测试点 $2\sim 3$ 的限制。

输入 #4/输出 #4

见下发样例的 sample_runplus4.in/sample_runplus4.out，该样例满足测试点 $4\sim 6$ 的限制。

输入 #5/输出 #5

见下发样例的 sample_runplus5.in/sample_runplus5.out，该样例满足测试点 $7\sim 10$ 的限制。

输入 #6/输出 #6

见下发样例的 sample_runplus6.in/sample_runplus6.out，该样例满足测试点 $15\sim 20$ 的限制。

说明/提示

样例 #1 说明

输入 #1 解密后为

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

在第一天中，$1$ 距离 $3$ 最近，贡献为 $1\times 1=1$ ；$2$ 距离 $3$ 最近，贡献为 $2\times 2=4$ ；$3$ 距离 $3$ 最近，贡献为 $3\times 0=0$ ；$4$ 距离 $4$ 最近，贡献为 $4\times0=0$ ；$5$ 距离 $3$ 最近，贡献为 $5\times 1=5$ 。故答案为 $1+4+0+0+5=10$

数据范围

对于 100% 的数据，$1\leq n\leq 2e5$ ，$1\leq m\leq 1e5$ ，$1\leq \Sigma num\leq 6e5$ ，$0\leq cnt_i\leq 1e3$ ，$0\leq w_i\leq 1e3$ ，$1\leq t_{i,j}\leq n$

测试点编号	$n$	$m$	$\Sigma num$	特殊性质
$1$	$\leq 5e3$	$\leq 1e3$	$\leq 6e3$	无
$2\sim3$			$\leq 6e5$
$4\sim 6$	$\leq 2e5$	$\leq 1e5$		$\forall _{i=2}^n$ $i$ 与 $i-1$ 直接连边
$7\sim 10$				$w_i=1$
$11\sim 14$	$\leq 5e4$	$\leq 3e4$	$\leq 2e5$	无
$15\sim 20$	$\leq 2e5$	$\leq 1e5$	$\leq 6e5$