KOI 城市在新冠疫情中遭受了很大损失，希望为未来可能发生的大流行做好充分准备。因此，KOI 城市希望分析当前的城市结构对病毒的脆弱程度。

KOI 城市由 $N$ 个地点和 $N-1$ 条双向道路组成，任意两个不同地点都可以仅通过道路往返。因此，城市的道路网络构成一棵树。各地点用从 $0$ 到 $N-1$ 的不同整数编号。由于道路网络是一棵树，从地点 $u$ 到地点 $v$ 的简单路径唯一。定义 $u$ 与 $v$ 的距离为这条路径上的边数。

KOI 城市中住着 $M$ 个人。对于所有 $0\le j\le M-1$，第 $j$ 个人住在地点 $P[j]$，可以前往与该地点距离不超过 $D[j]$ 的地点。

城市的病毒学家如下建立两个人之间的病毒传播模型。对于所有 $0\le v\le N-1$，地点 $v$ 的传播时间为正整数 $C[v]$。假设第 $j$ 个人在时刻 $t$ 首次感染，考虑其向第 $k$ 个人传播病毒。如果两个人都能前往地点 $w$，即 $w$ 到 $P[j]$ 的距离不超过 $D[j]$、到 $P[k]$ 的距离不超过 $D[k]$，那么地点 $w$ 就是一个传播媒介。

如果不存在传播媒介地点，第 $k$ 个人不会被第 $j$ 个人直接感染，但仍可能通过其他人间接感染。否则，设 $x$ 是所有媒介地点中传播时间最小的一个地点。如果第 $k$ 个人在时刻 $t+C[x]$ 尚未感染，则会在该时刻被第 $j$ 个人感染。对于所有不同的人组成的数对 $0\le j,k\le M-1$、$j\ne k$，病毒均按这种方式传播。

在上述模型下，研究人员想计算当第 $0$ 个人在时刻 $0$ 感染时，其他人会在何时感染。对于所有 $0\le j\le M-1$，你需要计算第 $j$ 个人首次感染的时刻。如果这个人永远不会感染，则记录为 $-1$。

实现细节

你需要实现以下函数。

vector<long long> find_spread(int N, int M, vector<int> A, vector<int> B,
vector<int> P, vector<int> D, vector<int> C)

• $N$：KOI 城市中的地点数量。
• $M$：KOI 城市中的人数。
• $A,B$：长度为 $N-1$ 的数组。对于所有 $0\le i\le N-2$，有一条道路连接地点 $A[i]$ 和 $B[i]$。每条道路在这两个数组中恰好出现一次。
• $P,D$：长度为 $M$ 的数组。对于所有 $0\le j\le M-1$，第 $j$ 个人住在地点 $P[j]$，可以前往与其距离不超过 $D[j]$ 的地点。
• $C$：长度为 $N$ 的数组。对于所有 $0\le v\le N-1$，地点 $v$ 的传播时间为 $C[v]$。
• 函数应返回一个长度为 $M$ 的数组 $T$。对于所有 $0\le j\le M-1$，如果第 $j$ 个人会感染，则 $T[j]$ 为其首次感染时刻，否则为 $-1$。
• 每个测试用例只调用此函数一次。

提交的源代码中的任何位置都不得调用输入输出函数。

数据范围

• $1\le N\le100\,000$
• $1\le M\le100\,000$
• 对于所有 $0\le i\le N-2$， $0\le A[i],B[i]\le N-1$, $A[i]\ne B[i]$.
• 对于所有 $0\le j\le M-1$， $0\le P[j],D[j]\le N-1$.
• 对于所有 $0\le v\le N-1$， $1\le C[v]\le10^9$.

子任务

1. (5 分)

   • $N\le500$, $M\le500$.
   • 对于所有 $0\le i\le N-2$， $A[i]=i$, $B[i]=i+1$.

2. (8 分)

   • $N\le5\,000$, $M\le5\,000$.
   • 对于所有 $0\le i\le N-2$， $A[i]=i$, $B[i]=i+1$.

3. (27 分)

   • 对于所有 $0\le i\le N-2$， $A[i]=i$, $B[i]=i+1$.

4. (5 分)

   • $N\le500$, $M\le500$.

5. (8 分)

   • $N\le5\,000$, $M\le5\,000$.

6. (47 分)

   • 没有额外限制。

样例

样例 1

考虑以下情况： $N=8$, $M=5$, $A=[0,1,2,3,4,5,6]$, $B=[1,2,3,4,5,6,7]$, $P=[2,5,7,1,4]$, $D=[2,0,0,1,1]$, $C=[40,5,5,16,32,8,1,10]$.

评测程序如下调用函数。

find_spread(8, 5, [0, 1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6, 7], [2, 5, 7, 1,
4], [2, 0, 0, 1, 1], [40, 5, 5, 16, 32, 8, 1, 10])

此时病毒按以下方式传播。

• 第 $0$ 个人在时刻 $0$ 感染。
• 第 $3$ 个人在时刻 $5$ 被第 $0$ 个人感染，传播媒介为地点 $1$。（地点 $2$ 也可以作为传播媒介。）
• 第 $4$ 个人在时刻 $16$ 被第 $0$ 个人感染，传播媒介为地点 $3$。
• 第 $1$ 个人在时刻 $24$ 被第 $4$ 个人感染，传播媒介为地点 $5$。
• 第 $2$ 个人始终不会感染。

函数应返回 $[0,24,-1,5,16]$.

样例 2

评测程序如下调用函数。

find_spread(8, 5, [0, 1, 2, 3, 4, 3, 3], [1, 2, 3, 4, 5, 6, 7], [2, 5, 7, 1,
4], [2, 0, 0, 1, 1], [40, 5, 5, 16, 32, 8, 1, 10])

函数应返回 $[0,24,10,5,16]$.

样例 3

评测程序如下调用函数。

find_spread(10, 10, [9, 0, 1, 5, 3, 8, 0, 6, 0], [3, 6, 8, 1, 2, 7, 4, 5, 9],
[9, 7, 1, 8, 6, 1, 4, 7, 5, 5], [0, 2, 0, 1, 3, 2, 6, 2, 1, 4], [10, 12, 5, 9,
8, 21, 20, 6, 13, 5])

函数应返回 $[0,11,17,11,5,11,5,11,17,5]$.

样例 4

评测程序如下调用函数。

find_spread(1, 2, [], [], [0, 0], [0, 0], [1000000000])

函数应返回 $[0,1000000000]$.

样例评测程序

样例评测程序按以下格式读入输入。

• 行 $1$: $N\ M$.
• 行 $2+i\quad(0\le i\le N-2)$: $A[i]\ B[i]$.
• 行 $1+N+j\quad(0\le j\le M-1)$: $P[j]\ D[j]$.
• 行 $1+N+M$: $C[0]\ C[1]\ \ldots\ C[N-1]$.

样例评测程序输出以下内容。

• 行 $1+j\quad(0\le j\le M-1)$: 函数 find_spread 返回数组中下标为 $j$ 的元素。

注意，样例评测程序可能与实际评测使用的评测程序不同。