You are given a tree containing N vertices. The vertices are numbered from 1 to N. A tree with N vertices is an undirected connected graph with exactly N−1 edges. Each vertex of the tree contains a lowercase English letter.
You will be asked Q queries. In each query, you will be given two integers U and V, denoting two vertices of the tree and a string S containing lowercase English letters. You will build a new string T by writing down the letters sequentially which are in vertices of the simple path from U to V. You have to say whether S is a subsequence of T or not.
Recall that, the subsequence of the string A is a string B that can be obtained from A by removing some (possibly zero) amount of characters.
Input
The first line contains two integers N (1 ≤ N ≤ 200000) and Q (1 ≤ Q ≤ 200000).
The next line contains a string of length N. The ith character of the string denotes the letter written on the ith vertex. It is guaranteed that all the characters of the string are lowercase English letters.
Each of the next N-1 lines contain two integers A(1 ≤ A ≤ N) and B(1 ≤ B ≤ N), denoting the edges of the tree.
Each of the next Q lines contain two integers U(1 ≤ U ≤ N) and V(1 ≤ V ≤ N) and a string S(1 ≤ |S| ≤ 200000) containing lowercase English letters.
It is guaranteed that the sum of lengths of S in all queries will not exceed 1000000.
Output
For each query, print "Yes" (without quotation marks) if S is a subsequence of T. Otherwise, print "No" (without quotation marks).
Sample
| Input | Output |
|---|---|
5 4 abcbb 1 2 1 5 2 3 2 4 3 5 cbb 3 5 bba 5 3 cbb 3 4 cbb | Yes No No Yes |
Query 1: From the path (3 -> 2 -> 1 -> 5), we get T = cbab, which contains cbb as a subsequence. Query 2: From the path (3 -> 2 -> 1 -> 5), we get T = cbab. bba is not a subsequence of cbab. Query 3: From the path (5 -> 1 -> 2 -> 3), we get T = babc. cbb is not a subsequence of babc. Query 4: From the path (3 -> 2 -> 4), we get T = cbb, which contains cbb as a subsequence. | |
