Cho một cây gồm ~n~ đỉnh, mỗi đỉnh được gán một chữ cái tiếng Anh thường. Với hai đỉnh ~u~ và ~v~, định nghĩa ~word(u, v)~ là xâu thu được khi đi theo đường đi đơn từ ~u~ đến ~v~ và ghi lại nhãn của các đỉnh theo đúng thứ tự đi qua.

Có ~q~ truy vấn. Mỗi truy vấn gồm bốn đỉnh ~u~, ~v~, ~x~, ~y~. Cần kiểm tra:

~word(u, v) = word(x, y)~

hay không.

Yêu cầu

Với mỗi truy vấn, in YES nếu hai xâu đường đi bằng nhau, ngược lại in NO.

Dữ liệu

Dữ liệu vào từ chuẩn gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• Dòng thứ hai chứa xâu ~c~ độ dài ~n~, trong đó ~c_i~ là nhãn của đỉnh ~i~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a~ và ~b~ mô tả một cạnh của cây.
• ~q~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~u~, ~v~, ~x~, ~y~.

Kết quả

Ghi ra ~q~ dòng, mỗi dòng là YES hoặc NO.

Ví dụ

Ví dụ 1

Input

7 5
abacaba
1 2
1 3
2 4
2 5
3 6
3 7
4 5 6 7
4 1 1 7
4 2 2 4
5 1 6 3
4 6 5 7

Output

YES
NO
NO
YES
NO

Giải thích

Ví dụ 1

~word(4,5) = \text{aca}~ và ~word(6,7) = \text{aca}~, nên truy vấn đầu tiên có kết quả YES.

~word(5,1) = \text{ba}~ và ~word(6,3) = \text{ba}~, nên truy vấn thứ tư có kết quả YES.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, q \le 2 \cdot 10^5~.
• ~c~ chỉ gồm chữ cái tiếng Anh thường.
• Dữ liệu cạnh tạo thành một cây.
• Mọi đỉnh trong truy vấn đều thuộc đoạn ~[1, n]~.

Chấm điểm

• Subtask~1~ ~(20\%)~: ~n, q \le 2000~.
• Subtask~2~ ~(20\%)~: cây là một đường thẳng.
• Subtask~3~ ~(25\%)~: mọi truy vấn có một đầu mút là gốc ~1~.
• Subtask~4~ ~(35\%)~: không có ràng buộc bổ sung.