Limits 2s, 512 MB

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 have to perform Q operations on the tree. There are two types of operations:

1. Update: You will be given a vertex U and a character C. You will update the character written on vertex U with C.

2. 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 contains two integers A(1 ≤ A ≤ N) and B(1 ≤ B ≤ N), denoting the edges of the tree.

In the next Q lines each, it will contain an integer TYPE, denoting the type of the operation.

If TYPE = 1, the line will contain an integer U(1 ≤ U ≤ N) and a lowercase English character C.

If TYPE = 2, the line will 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 length of S in all queries of type 2 will not exceed 1000000.

Output

For each query of TYPE 2, print "Yes" (without quotation marks) if S is a subsequence of T. Otherwise, print "No" (without quotation marks).

Sample

InputOutput
5 6
abcbb
1 2
1 5
2 3
2 4
2 3 5 cbb
2 3 5 bba
2 5 3 cbb
2 3 4 cbb
1 2 a
2 3 4 cbb
Yes
No
No
Yes
No

Submit

Login to submit.

Statistics

80% Solution Ratio
dip_BRUREarliest, Dec '19
Kuddus.6068Fastest, 0.2s
Nafis_ShhriarLightest, 106 MB
Shahe_NoorShortest, 6243B
Toph uses cookies. By continuing you agree to our Cookie Policy.