John has got a tree with N vertices. The vertices are numbered from 1 to N. He considers vertex 1 as the root of the tree. Each vertex of the tree contains a character C.

Now John is doing a weird experiment with this tree.

He often changes the character of a node in the tree and then sometimes he randomly selects a node v and tries to form a palindrome with all the characters in the subtree of node v.

But since John is very busy man and has a lot of other important experiments to do he needs your help on this one.

Input

First line of the input contains an integer N (1 <= N <= 100000) denoting the number of vertices.

Next N-1 lines contains two integers A and B (1 <= A, B <= N) which means there is an edge between vertex A and B.

Next line contains a string of length N. The i^th character of this string denotes the character in node i.

Then there will be an integer M (1 <= M <= 100000) in a separate line denoting the number of queries. Next M lines will contain a query.

Each query will be in one of the following form:

0 x C: which means the character of node x has been changed to C.

1 x: which means you are asked to answer if a palindrome can be formed with all the characters in the sub tree of node x. There will be at least one query of this type.

Output

For each query of the form “1 x” print “YES” if a palindrome can be formed with all the characters in subtree of node x. Otherwise print “NO” (without the quotes).

All the characters in the input will be small letters of English alphabet, i.e. a, b, c ... x, y, z.

See sample input / output for details.

Sample

Input
7
5 4
1 5
6 3
1 7
5 6
6 2
abdaabc
7
1 1
1 5
1 3
0 7 a
1 1
0 4 z
1 5

output
NO
YES
YES
YES
NO

Explanation

In the 2^nd query, the formed palindrome can be “badab” or “abdba”.

In the 3^rd query, there is only 1 character “d”, which is a palindrome.