Because the KOI city suffered significant damage from the recent COVID-19 pandemic, it intends to thoroughly prepare for future pandemic situations. To this end, the KOI city wants to analyze how vulnerable its current urban structure is to a virus.

The KOI city consists of $N$ locations and $N - 1$ bidirectional roads, and any two distinct locations can be reached using only the roads. In other words, the city's road network forms a tree structure. Each location is identified by a distinct integer between $0$ and $N - 1$. Since the city's road network is a tree, for any two locations $u$ and $v$, there is a unique simple path from location $u$ to location $v$. Let the number of edges in this unique path be defined as the distance between $u$ and $v$.

There are $M$ people living in the KOI city. For every $0 \le j \le M - 1$, person $j$ lives at location $P[j]$ and can travel to any location whose distance from that location is at most $D[j]$.

Virologists in the KOI city modeled the process of virus transmission between two people as follows. For every $0 \le v \le N - 1$, the transmission time at location $v$ is represented by a positive integer $C[v]$. Suppose person $j$ was first infected with the virus at time $t$, and let person $k$ be the person who receives the virus from person $j$. If location $w$ can be reached by both person $j$ and person $k$—that is, if the distance between $w$ and location $P[j]$ is at most $D[j]$ and the distance between $w$ and location $P[k]$ is at most $D[k]$—then location $w$ becomes a medium of transmission.

If there is no location that serves as a medium of transmission, person $k$ is not directly infected with the virus by person $j$. (Of course, they can be indirectly infected through another person.) If there are locations that serve as a medium of transmission, let $x$ be the number of the location among them that minimizes the transmission time. If person $k$ is not infected with the virus at time $t + C[x]$, then person $k$ is infected with the virus by person $j$ at that time. The virus spreads in this manner for all pairs of distinct people $0 \le j, k \le M - 1, j \neq k$.

Under the above model, the researchers of the KOI city want to calculate when other people are infected with the virus when person $0$ is infected at time $0$. You must calculate the time when each person $j$ is first infected with the virus for all $0 \le j \le M - 1$. However, if person $j$ is not infected with the virus, you must record that time as $-1$.

Implementation Details

You must implement the following function:

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$: The number of locations in the KOI city.
• $M$: The number of people in the KOI city.
• $A, B$: Arrays of length $N - 1$. For every $i$ ($0 \le i \le N - 2$), there exists a road connecting location $A[i]$ and location $B[i]$. Every road appears exactly once in both arrays.
• $P, D$: Arrays of length $M$. For every $j$ ($0 \le j \le M - 1$), person $j$ lives at location $P[j]$ and can travel to any location whose distance from that location is at most $D[j]$.
• $C$: An array of length $N$. For every $v$ ($0 \le v \le N - 1$), the transmission time at location $v$ is $C[v]$.
• This function must return an array $T$ of size $M$. For every $j$ ($0 \le j \le M - 1$), $T[j]$ should be the time when person $j$ is first infected with the virus if they are infected, and $-1$ if they are not infected.
• This function is called exactly once for each test case.

Do not execute any input/output functions in any part of the source code you submit.

Constraints

• $1 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• For all $0 \le i \le N - 2$, $0 \le A[i], B[i] \le N - 1$, $A[i] \neq B[i]$
• For all $0 \le j \le M - 1$, $0 \le P[j], D[j] \le N - 1$
• For all $0 \le v \le N - 1$, $1 \le C[v] \le 10^9$

Subtasks

1. (5 points) $N \le 500, M \le 500$, and for all $0 \le i \le N - 2$, $A[i] = i, B[i] = i + 1$.
2. (8 points) $N \le 5\,000, M \le 5\,000$, and for all $0 \le i \le N - 2$, $A[i] = i, B[i] = i + 1$.
3. (27 points) For all $0 \le i \le N - 2$, $A[i] = i, B[i] = i + 1$.
4. (5 points) $N \le 500, M \le 500$.
5. (8 points) $N \le 5\,000, M \le 5\,000$.
6. (47 points) No additional constraints.

Examples

Input 1

8 5
0 1
1 2
2 3
3 4
4 5
5 6
6 7
2 2
5 0
7 0
1 1
4 1
40 5 5 16 32 8 1 10

Output 1

0
24
-1
5
16

Input 2

8 5
0 1
1 2
2 3
3 4
4 5
3 6
3 7
2 2
5 0
7 0
1 1
4 1
40 5 5 16 32 8 1 10

Output 2

0
24
10
5
16

Input 3

10 10
9 3
0 6
1 8
5 1
3 2
8 7
0 4
6 5
0 9
9 0
7 2
1 0
8 1
6 3
1 2
4 6
7 2
5 1
5 4
10 12 5 9 8 21 20 6 13 5

Output 3

0
11
17
11
5
11
5
11
17
5

Input 4

1 2
0 0
0 0
1000000000

Output 4

0
1000000000

Sample grader

The sample grader receives input in the following format:

• Line 1: $N$ $M$
• Line $2 + i$ ($0 \le i \le N - 2$): $A[i]$ $B[i]$
• Line $1 + N + j$ ($0 \le j \le M - 1$): $P[j]$ $D[j]$
• Line $1 + N + M$: $C[0]$ $C[1]$ $\dots$ $C[N - 1]$

The sample grader outputs the following:

• Line $1 + j$ ($0 \le j \le M - 1$): The $j$-th element of the array returned by the function find_spread.

Note that the sample grader may differ from the actual grader used for evaluation.