Larry the magical panda has recently purchased a ski resort. Being an avid fan of bamboo trees, he ensured that the ski hills resembled a rooted tree. There are breakpoints, which are given a unique ID from
to
inclusive. The breakpoint with the ID
will always be the root. There are
hills, which connect these breakpoints. The
-th hill has a difficulty level of
. There will be
fellow pandas, the
-th of which with a skill level of
, who will start at breakpoint
and begin skiing. The following process is used by them to determine which hill they will go down:
- If there are no hills connecting to their current breakpoint, they will stop skiing. Note that a panda will never use a hill that they have already used (otherwise, they would be going uphill).
- The panda will consider all difficulty levels of the hills connecting to their breakpoint, and will go down the hill that minimizes
. If there is a tie, they will go down the hill with the lower difficulty level. Out of the hills that they consider, there will never be two with equal difficulty.
- Go back to step 1.
Larry wants you to help him determine how many pandas will visit each breakpoint so he can efficiently determine how to ambush all the skiers.
Constraints
A panda will never have to choose between two hills of equal difficulty.
Input Specification
The first line contains integers
and
.
The next lines contain
integers,
,
, and
, representing a hill between breakpoint
and
with a difficulty level of
.
The next line contains integers
, representing the skill level of the pandas.
Output Specification
Output a single line containing integers, with the
-th integer denoting the number of pandas who will visit the
-th breakpoint.
Sample Input 1
5 6
1 2 5
1 3 6
2 4 1
2 5 2
1 2 3 4 5 6
Sample Output 1
6 5 1 1 4
Sample Input 2
8 6
1 2 3
2 3 3
2 4 4
4 5 1
4 6 3
2 7 6
1 8 4
1 2 3 4 5 6
Sample Output 2
6 3 3 0 0 0 0 3
Comments