KOI 市在经历过新冠疫情的重创后，希望为未来可能发生的疫情做好充分准备。为此，KOI 市想要分析其当前的城市结构在病毒面前的脆弱程度。

KOI 市由 $N$ 个地点和 $N - 1$ 条双向道路组成，任意两个不同的地点之间都可以仅通过道路往返。也就是说，城市的道路网构成了一个树状结构。每个地点由 $0$ 到 $N - 1$ 之间互不相同的整数标识。由于城市的道路网是一棵树，对于任意两个地点 $u, v$，从 $u$ 号地点到 $v$ 号地点的简单路径是唯一的。我们将这条唯一路径上的边数定义为 $u$ 和 $v$ 的距离。

KOI 市居住着 $M$ 名居民。对于所有 $0 \le j \le M - 1$，第 $j$ 号居民住在 $P[j]$ 号地点，并且可以在该地点距离 $D[j]$ 以内的所有地点之间往返。

KOI 市的病毒学家对两人之间病毒传播的过程建模如下： 对于所有 $0 \le v \le N - 1$，地点 $v$ 的传播时间由一个正整数 $C[v]$ 表示。假设第 $j$ 号居民在时刻 $t$ 首次感染病毒，并设将病毒传播给第 $k$ 号居民的人是第 $j$ 号居民。如果 $w$ 号地点是第 $j$ 号居民和第 $k$ 号居民可以共同往返的地点——换句话说，如果 $w$ 号地点与 $P[j]$ 号地点的距离不超过 $D[j]$，且 $w$ 号地点与 $P[k]$ 号地点的距离不超过 $D[k]$，则 $w$ 号地点成为传播的媒介。

如果没有地点可以作为传播媒介，则第 $k$ 号居民不会直接从第 $j$ 号居民那里感染病毒。（当然，可以通过其他人间接感染）。如果有地点可以作为传播媒介，设这些地点中传播时间最小的地点编号为 $x$。如果第 $k$ 号居民在时刻 $t + C[x]$ 尚未感染病毒，则第 $k$ 号居民会在该时刻被第 $j$ 号居民感染。病毒以这种方式在所有不同的居民对 $0 \le j, k \le M - 1, j \neq k$ 之间扩散。

在上述模型下，KOI 市的研究人员想要计算当第 $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$ 的数组。对于所有 $i$ ($0 \le i \le N - 2$)，存在一条连接 $A[i]$ 号地点和 $B[i]$ 号地点的道路。所有道路在两个数组中恰好出现一次。
• $P, D$: 长度为 $M$ 的数组。对于所有 $j$ ($0 \le j \le M - 1$)，第 $j$ 号居民住在 $P[j]$ 号地点，且可以在该地点距离 $D[j]$ 以内的地点往返。
• $C$: 长度为 $N$ 的数组。对于所有 $v$ ($0 \le v \le N - 1$)，地点 $v$ 的传播时间为 $C[v]$。
• 该函数应返回一个大小为 $M$ 的数组 $T$。对于所有 $j$ ($0 \le j \le M - 1$)，$T[j]$ 应为第 $j$ 号居民首次感染病毒的时刻；如果未感染，则为 $-1$。
• 该函数在每个测试用例中仅被调用一次。

在提交的源代码中，不得执行任何输入输出函数。

数据范围

• $1 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• 对于所有 $0 \le i \le N - 2$，$0 \le A[i], B[i] \le N - 1, A[i] \neq 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] \le 10^9$

子任务

1. (5分) $N \le 500, M \le 500$，且对于所有 $0 \le i \le N - 2$，$A[i] = i, B[i] = i + 1$。
2. (8分) $N \le 5\,000, M \le 5\,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 \le 500, M \le 500$。
5. (8分) $N \le 5\,000, M \le 5\,000$。
6. (47分) 无额外限制。

样例

输入格式 1

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])

输出格式 1

[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])

输出格式 2

[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])

输出格式 3

[0, 11, 17, 11, 5, 11, 5, 11, 17, 5]

输入格式 4

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

输出格式 4

[0, 1000000000]