Đất nước VNOI là một quốc đảo tuyệt đẹp với dòng nước biển xanh biếc và các bãi cát trắng trải dài vô tận. Đất nước bao gồm ~n~ hòn đảo được kết nối với nhau bởi ~n-1~ cây cầu đảm bảo luôn có đường đi giữa hai hòn đảo bất kì. Nhân mùa du lịch năm ~2023~ chuẩn bị đến, chính phủ VNOI ban hành một chính sách đặc biệt nhằm thu hút khách du lịch: Mỗi du khách khi đến thăm hòn đảo thứ ~i~ sẽ nhận được một phần quà đặc biệt là một kí tự ~c_i~.

Ngay sau khi chính sách được ban hành, đã có hàng loạt du khách đặt vé du lịch đến đất nước VNOI. Chính phủ VNOI tính toán được rằng, sẽ có ~Q~ vị khách du lịch ghé thăm đất nước. Vị khách thứ ~i~ sẽ bắt đầu chuyến thăm quan của mình tại hòn đảo ~u_i~ và anh ta muốn thu thập được các món quà lần lượt được thể hiện qua xâu ~s_i~. Hành trình của vị khách sẽ bắt đầu tại hòn đảo ~u_i~ và đi qua một số hòn đảo sao cho không có hòn đảo nào được đi qua ~2~ lần. Tuy nhiên, do hiện nay đang diễn ra đại chiến ICPC tại hòn đảo thứ ~1~ nên các du khách sẽ muốn hạn chế lại gần hòn đảo này. Vì thế hành trình du lịch của vị khách thứ ~i~ sẽ không được phép đi qua các hòn đảo có khoảng cách đến hòn đảo thứ ~1~ nhỏ hơn khoảng cách từ hòn đảo ~u_i~ đến hòn đảo thứ ~1~.

Yêu cầu: Với mỗi vị khách du lịch hãy giúp chính phủ VNOI tính toán số lượng hành trình du lịch thỏa mãn mong muốn của vị khách ấy nhé!

Input

Vào từ file văn bản str.inp:

• Dòng đầu tiên chứa số ~n~ và ~Q~ cho biết số hòn đảo và số lượng du khách đến thăm đất nước VNOI ~(1 \leq n,Q \leq 2 \cdot 10^5)~.

• Dòng thứ hai chứa ~n~ kí tự ~c_i~ (~c_i~ là một kí tự tiếng Anh in thường) thể hiện các phần quà nhận được khi đến hòn đảo ~i~.

• ~n - 1~ dòng tiếp theo mỗi dòng chứa 2 số ~u~ ~v~ thể hiện có cây cầu kết nối giữa hòn đảo ~u~ và hòn đảo ~v~ ~(1 \leq u,v \leq n)~.

• ~Q~ dòng cuối, dòng thứ ~i~ chứa hòn đảo bắt đầu ~u_i~ và xâu thể hiện dãy các món quà mà vị khách thứ ~i~ muốn thu thập.

Dữ liệu đảm bảo tổng độ dài các xâu ~s_i \leq 5 \cdot 10^5~.

Output

Đưa ra file văn bản str.out ~Q~ dòng:

• Dòng thứ ~i~ thể hiện số lượng hành trình thỏa mãn yêu cầu của vị khách thứ ~i~.

Scoring

Gọi S là tổng độ dài các xâu ~s_i~.

Sample Input 1

10 10
iotmmoomoo
6 8
5 7
9 4
2 4
4 7
10 3
7 1
8 10
8 7
7 omo
7 omo
1 iomo
7 omo
1 iomo
1 iomo
1 iomo
1 iomo
1 iomo
7 omo

Sample Output 1

4
4
4
4
4
4
4
4
4
4