The country of IOI consists of $N$ cities and $N - 1$ bidirectional roads connecting them, such that any two distinct cities can be reached from each other using only the roads. In other words, the road network of IOI forms a tree structure.

Each city is assigned a unique number from $0$ to $N - 1$, and city $0$ is the capital of IOI. For all $0 \le i \le N - 2$, the $i$-th road connects city $U[i]$ and city $V[i]$, and the length of the road is $W[i]$ km.

In the country of IOI, taxi fares vary by city. Specifically, for all $0 \le i \le N - 1$, a taxi departing from city $i$ has a base fare of $A[i]$ and a fare per km of $B[i]$. This means that if you start a taxi ride from city $i$ and travel $d$ km, you must pay $A[i] + d \times B[i]$.

Seohyun currently lives in the capital, city $0$. Seohyun intends to travel to other cities by taxi. When Seohyun arrives at a city, she can either continue in the same taxi or switch to a taxi departing from that city. Of course, if she switches taxis, she must pay the base fare, and the fare per km may also change. Calculate the minimum cost required to travel from city $0$ to all other cities.

Implementation Details

You must implement the following function:

vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U,
vector<int> V, vector<int> W)

• This function is called exactly once.
• $A$: An integer array of size $N$. For all $i$ ($0 \le i \le N - 1$), $A[i]$ is the base fare of a taxi departing from city $i$.
• $B$: An integer array of size $N$. For all $i$ ($0 \le i \le N - 1$), $B[i]$ is the fare per km of a taxi departing from city $i$.
• $U, V, W$: Integer arrays of size $N - 1$. For all $i$ ($0 \le i \le N - 2$), there is a road of length $W[i]$ km connecting city $U[i]$ and city $V[i]$.
• This function must return an array $C$ of size $N - 1$. For all $i$ ($0 \le i \le N - 2$), $C[i]$ must be equal to the minimum cost required to travel from city $0$ to city $i + 1$.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $2 \le N \le 100\,000$
• $0 \le A[i] \le 10^{12}$ for all $i$ ($0 \le i \le N - 1$)
• $0 \le B[i] \le 1\,000\,000$ for all $i$ ($0 \le i \le N - 1$)
• $0 \le U[i], V[i] \le N - 1$; $U[i] \neq V[i]$ for all $i$ ($0 \le i \le N - 2$)
• $1 \le W[i] \le 1\,000\,000$ for all $i$ ($0 \le i \le N - 2$)

Subtasks

1. (7 points) $N \le 20$
2. (8 points) $U[i] = i; V[i] = i + 1$ for all $i$ ($0 \le i \le N - 2$)
3. (13 points) $N \le 2\,000$
4. (17 points) $B[i] \le 30$ for all $i$ ($0 \le i \le N - 1$)
5. (29 points) There are at most $2\,000$ indices $i$ such that $B[i] = 0$ ($0 \le i \le N - 1$)
6. (26 points) No additional constraints.

Examples

Input 1

5
10 5 13 4 3
10 7 5 9 1
1 0
0 2
3 2
2 4
1 5 10 3

Output 1

20 60 104 88

Note

• To travel from city $0$ to city $1$, the optimal method is to take a taxi from city $0$ to city $1$, with a total cost of $20$.
• To travel from city $0$ to city $2$, the optimal method is to take a taxi from city $0$ to city $2$, with a total cost of $60$.
• To travel from city $0$ to city $4$, the optimal method is to take a taxi from city $0$ to city $1$, switch taxis, and then travel through city $0$ and city $2$ to city $4$, with a total cost of $88$.
• To travel from city $0$ to city $3$, the optimal method is to take a taxi from city $0$ to city $1$, switch taxis, travel through city $0$ and city $2$ to city $4$, switch taxis again, and travel through city $2$ to city $3$, with a total cost of $104$.

Sample Grader

The sample grader receives input in the following format:

• Line 1: $N$
• Line 2: $A[0] \ A[1] \ \dots \ A[N - 1]$
• Line 3: $B[0] \ B[1] \ \dots \ B[N - 1]$
• Line 4 + $i$ ($0 \le i \le N - 2$): $U[i] \ V[i] \ W[i]$

The sample grader outputs the following:

• Line $i$: The $i$-th element of the array returned by travel.

Note that the sample grader may differ from the grader used in actual grading.