Cho một cây có ~ n ~ nút, các nút được đánh số từ 1 đến ~ n ~, nút 1 là nút gốc của cây. Mỗi nút trên cây có giá trị là 1 chữ cái tiếng anh in thường. Có q truy vấn, mỗi truy vấn dạng:

• ~ x~ ~s ~: trong đó ~ x ~ là gốc cây con và ~ s ~ là một xâu.

Với mỗi truy vấn, gọi ~ t ~ là xâu được xây dựng bằng cách lấy tất cả các ký tự trong cây con gốc ~ x ~, mỗi nút được lấy chính xác 1 lần. Yêu cầu tính số lượng ký tự nhỏ nhất thêm vào xâu ~ t ~ để từ ~ t ~ xây dựng được xâu ~ s ~.

Dữ liệu vào

• Dòng đầu tiên ghi 2 số nguyên ~ n, q ~ ~ ( 2 ≤ n ≤ 10^5; 1 ≤ q ≤ 10^5 ) ~
• Dòng thứ 2 ghi ~ n ~ ký tự chữ cái in thường, trong đó ký tự thứ ~ i ~ ~ ( i = 1…n ) ~ là giá trị của nút thứ ~ i ~ trên cây, các chữ cái cách nhau 1 dấu cách.
• ~ n -1 ~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~ x, y ~ cho biết một cạnh trên cây.
• Tiếp theo là ~ q ~ dòng, mỗi dòng là 1 truy vấn dạng ~ u, s ~.

Tổng độ dài của các xâu trong truy vấn không vượt quá ~ 10^6 ~

Kết quả

• Ghi trên ~ q ~ dòng, mỗi dòng một số nguyên là câu trả lời cho truy vấn tương ứng trong input.

Ví dụ:

Input 1

8 3
o v s l v p d i
1 3
8 3
4 8
6 1
5 3
7 6
2 3
7 ifwrxl
4 eyljywnm
3 llvse 

Output 1

6
7
2