#4 「 文明 」

统计

R君在继续着罗辑的宇宙社会学的研究,R君发现是否为善意的文明与他们的距离到本文明的距离的奇偶有很大的关系。

所以R君提出了如下简化的问题,考虑一个n个节点带边权的树,两点间距离是两点间树上路径的边权和。

R君想知道对于一个点来说,到这个点是距离奇数的节点的距离和,与到这个点距离是偶数的节点的距离和。

输入格式

第一行包含两个整数$n$, $q$。$q$表示询问数量。

接下来$n-1$行,每行三个数字$(x,y,z)$表示$x$与$y$之间的距离是$z$。

接下来$q$行,每行一个整数$x$,表示询问的节点为$x$。

输出格式

输出包含$q$行,每行两个整数,分别表示距离为奇数的节点的距离和与距离为偶数的节点的距离和。

样例数据

input

4 4
1 2 1
2 3 2
2 4 3
1
2
3
4

output

4 4
4 2
8 2
8 4

样例解释

每个点到1号点的距离:0,1,3,4

每个点到2号点的距离:1,0,2,3

每个点到3号点的距离:3,2,0,5

每个点到4号点的距离:4,3,5,0

数据规模与约定

$1 \le n \le 10^5$, $q \le n$, $1 \le z \le 10^3$。

时间限制:1s

空间限制:512MB

Author: zrt