题目描述

小 Z 和 小 Y 收到了一颗漂亮的树，由 $n$ 个节点构成，编号 $1,2,\cdots,n$ ，其中 $1$ 号节点是树的根。

我们称节点 $u$ 是节点 $v$ 的祖先，当且仅当 $u$ 在 $v$ 到根的路径上（注意这里每个节点都是自己的祖先）。

我们定义 $subtree_u$ 表示 $u$ 的子树里的点集，也就是所有以 $u$ 为祖先的节点集。

现在小 Z 给了每个节点 $i$ 一个权值 $a_i$ ，小 Y 给了每个节点 $i$ 一个权值 $b_i$ 。

我们定义一个节点 $u$ 的价值为

$$ans_u=\sum_{x\in subtree_u}\sum_{y\in subtree_u} \min\{|a_x-a_y|,|b_x-b_y|\} \mod 10^9+7 $$

请你对每个节点 $u$ 求出其价值 $ans_u$ 。

输入格式

从 distance.in 文件读入数据。

第一行一个整数，代表树上的节点个数 $n$ 。

接下来 $n-1$ 行，每行两个整数 $u_i, v_i (1\le u_i,v_i\le n, u_i \neq v_i)$ ，代表树上的一条边连接节点 $u_i$ 和节点 $v_i$ 。保证输入的所有边构成了一棵树。

接下来 $n$ 行，每行两个整数 $a_i,b_i$ ，代表第 $i$ 个节点的两个权值。

输出格式

输出到 distance.out 文件。

共 $n$ 行，第 $i$ 行一个整数，表示 $ans_i$。

样例

5
1 2
1 3
2 4
2 5
9 5
2 8
7 1
4 3
6 6

44
12
0
0
0

样例 2

点击链接 ex_distance2.in 和 ex_distance2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于 $20\%$ 的测试点，保证 $1\le n\le 10,1\le a_i,b_i\le 10^9$ 。

对于另外 $20\%$ 的测试点，保证 $1\le n\le 100,1\le a_i,b_i\le 10^9$ 。

对于另外 $30\%$ 的测试点，保证 $1\le n\le 5000,1\le a_i,b_i\le 10^9$ 。

对于剩下 $30\%$ 的测试点，保证 $1\le n\le 5\times 10^5,1\le a_i,b_i\le 10^9$。