Devu is a little boy. He does not know how to take carries while adding two numbers in decimal base. eg. He will struggle in adding numbers 83 and 19, because
3 + 9 = 12 and he needs to take a carry of 1.

 

You are given an integer n. Can you write it in terms of sum of two positive integers such that while adding them in base 10, Devu doesn't need to use any carries.

 

Input

 

First line of the input contains an integer T denoting number of test cases.

 

For each test case, there is a single line containing an integer n.

 

Output

 

For each test case, print a single line YES or NO according to situation in the problem.

 

Constraints

 

• 1 = T = 1000
• 1 = n = 10^5

 

Example

Input: 2 1 9 Output: NO YES

Explanation

 

Example case 1. 1 can not written in desired way.

 

Example case 2. 9 can be written as sum of 2 and 7. Devu doesn't need to use any carries here.

q2

You are given a rooted tree with N nodes. Tree is rooted at node 1. Each node of the tree contains some value. Initially value of each node will be given.

 

You are given Q queries. Queries can be of two types, type U and type Q.

 

• Type U: This query is represented by U x v, which means that you
  have to add value v to node x.
• Type Q: This query is represented by Q x, which means that you
  have to output number of nodes in the subtree rooted at node x having value equal to zero.

 

Input

 

First line of the input contains two space separated integers N and Q.

 

For next N - 1 lines, each line contains two space separated integers u, v
denoting that there is an edge between u and v in the tree. It is guaranteed that 1 = u, v = N, u != v.
It is also guaranteed that no edge is repeated in the input.

 

Next line contains N space separated integers denoting the initial weight of each node in order, 1 to N. Weights will be between -10^9 to 10^9 (both inclusive).

 

For next Q lines, each line contains a query of either type U or type Q.

 

Output

 

For each query of type Q, output a single line containing an integer corresponding to answer of the query.

 

Constraints

 

• 1 = N, Q = 10^5
• For query of type U, -10^9 = v = 10^9
• For query of type U and V, 1 = x = N

 

Example

Input: 4 3 1 2 1 3 2 4 5 -2 0 3 Q 1 U 3 1 Q 1 Output: 1 0