Ada the Ladybug is currently on a trip on apple tree. There are many apples on the tree connected with branches. Each apple is inhabited by either Psylloideas or by Woolly Apple Aphids. Psylloideas and Aphids doesn't like each other, so it is strictly prohibited to walk from apple of Psylloideas to apple of aphids (and vice versa). Ada has some questions, whether it is possible to go from node I to node J.

Anyway note, that as Aphids and Psyllodeas doesn't like each other, they sometime conquer an apple of the others. Also note, that it is a real apple tree (not some bush) so no apple is connected with more than 50 other apples.

Input

The first line contains 1 ≤ N, Q ≤ 3*10⁵ , number apples on tree and number for queries.

The next line contains N characters (either 0 or 1), indicating whether i^th apple belongs to Psyllodeas or to Aphids.

Next N-1 lines contains two numbers, the branches (edges) of apple tree (0 ≤ I, J < N, I ≠ J).

Each of following Q lines contains one of following types of queries:

0 I, 0 ≤ I < N, meaning that ownership of I^th apple has changed.

1 I J, 0 ≤ I, J < N, question, whether it is possible to go from I^th to J^th apple.

Output

For each query of second kind (1) print "YES", if it is possible or "NO" if it is impossible!

Example Input

8 11
00111100
0 1
1 7
1 2
2 3
2 6
2 4
4 5
1 1 2
1 0 7
1 6 5
1 2 3
1 6 7
0 2
1 1 2
1 0 7
1 6 5
1 2 3
1 6 7

Example Output

NO
YES
NO
YES
NO
YES
YES
NO
NO
YES