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