Flowers

Jimmy’s company has $n$ plantations of flowers. For each of the plantations, we know the type of flowers that are cultivated and how many tons of flowers have been produced this year. We know that the flower plantations are connected by $n-1$ direct roads, so that each plantation is accessible from any another and there is only one way to go from plantation $x$ to plantation $y$, for every $1 \leq x, y \leq n$. In addition, we know the distance in kilometers for each of the $n-1$ direct connections.

Task

Jimmy wants to bring all the flowers of the same type in the same place, with minimal transport costs. If we have $a$ tons of flowers and we want to send them over a distance of $b$ kilometres, the transport cost is $a \cdot b$. For each type of flower, Jimmy wants to determine the minimal transport cost to bring all the flowers of this type together.

Input data

On the first line there will be the number $n$, then, on the second line, $n$ small letters separated from each other by a space, which symbolize the type of flower produced
on the plantation $i$ (each type of flower is a small letter in the English alphabet).

On the third line there are $n$ integer numbers which symbolize how many tons of this flower have been produced on the plantation $i$.

On each of the following $n-1$ lines, there are three natural numbers $x$, $y$, $d$ with the signification that there is a direct road between the plantations $x$ and $y$, while the number $d$, represents the distance from $x$ to $y$.

Output data

At the standard output, the first line will display $26$ integer numbers separated from each other by a space, the $i^\text{th}$ integer number representing the minimal transport cost for the type of flower which is specified by the letter on the position $i$ in the English alphabet (the answers are in the order of the letters of the alphabet).

Constraints and clarifications

• $4 \leq n \le 200 \ 000$
• Each of the numbers presented in the input is a natural number $\le 200 \ 000$.
• The final destination of each of the transports is in one of the $n$ existing plantations.
• If a small letter does not represent the code of a flower type, then the minimal transport cost for that type is $0$.
• For $20\%$ of the tests, $n < 1 \ 000$.
• For another $25\%$ of the tests, $n < 100 \ 000$.

Example

stdin

4
a b a b
2 4 4 3
1 3 4
3 4 2
1 2 5

stdout

8 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0