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.
A panda will never have to choose between two hills of equal difficulty.
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 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