Demenland bao gồm ~N~ thành phố được kết nối bởi ~N - 1~ con đường. Cũng có ~K~ cửa hàng, cửa hàng thứ ~i~ nằm ở thành phố ~a_i~. Vị trí của tất cả các cửa hàng đều khác biệt. Demen biết rằng khách hàng ~i~ sống ở thành phố ~i~. Khách hàng ~i~ có cửa hàng yêu thích nằm ở thành phố ~f_i~ và họ có giá trị kiên nhẫn là ~p_i~.

Ta quy ước rằng khoảng cách giữa 2 thành phố ~x~ và ~y~ là số con đường ít nhất cần phải đi qua để từ ~x~ đến ~y~ hoặc ngược lại. Với khách hàng thứ ~i~, giả sử khoảng cách từ thành phố ~i~ đến với cửa hàng gần nhất là ~d~. Nếu khoảng cách từ ~i~ đến ~f_i~ không vượt quá ~d + p_i~, khách hàng ~i~ sẽ ưu tiên đi đến thành phố ~f_i~. Ngược lại, họ sẽ đi đến cửa hàng gần nhất. Nếu có nhiều cửa hàng như thế, họ sẽ chọn một cửa hàng bất kỳ.

Bây giờ, Demen dự định sẽ khởi nghiệp với một cửa hàng, anh ấy cần chọn vị trí để xây cửa hàng đó. May mắn thay, Demen khá nổi tiếng nên nếu cửa hàng của anh ấy cùng gần nhất với nhiều cửa hàng khác tính từ thành phố ~i~, khách hàng ~i~ chắc chắn sẽ đi cửa hàng của Demen nếu không đi được cửa hàng yêu thích của họ. Demen đang cần tính xem nếu anh ấy xây dựng cửa hàng tại thành phố ~x~, sẽ có bao nhiêu khách hàng đến cửa hàng của anh ấy?

Input

• Dòng đầu tiên bao gồm 2 số nguyên dương ~N~ và ~K~ (~1 \leq K \leq N \leq 3 \cdot 10^5~).

• ~N - 1~ dòng tiếp, dòng thứ ~i~ chứa ~2~ số nguyên dương ~x_i~ và ~y_i~ mô tả có con đường nối giữa 2 thành phố này.

• Dòng tiếp theo chứa ~K~ số nguyên dương ~a_i~ (~1 \leq a_i \leq N~) chính là vị trí của ~K~ cửa hàng.

• N dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên dương ~f_i~ và ~p_i~ (~1 \leq f_i \leq N, 0 \leq p_i \leq N - 1~) lần lượt là cửa hàng yêu thích và giá trị kiên nhẫn của khách hàng ~i~.

Output

In ra ~N~ số nguyên dương, số thứ ~i~ chính là số khách hàng sẽ đến cửa hàng của Demen nếu anh ấy đặt cửa hàng tại thành phố ~i~.

Sample Input 1

4 1
1 2
1 3
2 4
1
1 1
1 0
1 1
1 0

Sample Output 1

0 2 0 1

Sample Input 2

6 3
1 2
2 3
3 4
4 5
5 6
1 2 6
6 3
6 1
6 2
1 4
2 0
1 1

Sample Output 2

1 1 1 1 1 2