Our social:

CodeChef | A Good Problem | August Challenge | Answer

Chef likes trees a lot. Now he thinking about one interesting problem on trees. He finds the following problem interesting, and you?
Given a tree T and Q queries to it. Tree T has N nodes numbered from 1 to N. Each node v has a value Avassociated with it. Queries can be one of three types.
  • 1 u v - reverse the values on the path between vertices u and v.
  • 2 ul ur vl vr - print "Yes" if all the values on the path from ul to ur are exactly same as that of path from vl to vr, and "No" otherwise. It is ensured that length of both the paths are same.
  • 3 ul ur vl vr - Copy all values on path from ul to ur and insert them into the path from vl to vr. It is ensured that length of both the paths are same.

Input

The first line contains two integers N and Q.
The second line contains N space-separeted integers denoting Av - the values associated with nodes.
Next N-1 lines contains two space-separeted integers uv denoting the nodes connected by an edge.

Next Q lines contains queries as described above.Image result for codechef


Output

For each query of second type output your answer in a single line.

Constraints

  • 1 ≤ N, Q ≤ 105
  • 1 ≤ Ai ≤ 103
  • 1 ≤ u, v, ul, ur, vl, vr ≤ N

Subtasks

  • Subtask 1: (21 pts) N, Q ≤ 25000.
  • Subtask 2: (79 pts) Original constraints.

Example

Input:
5 8
1 2 3 4 5
1 2
1 3
2 4
2 5
2 1 3 1 2
3 1 1 2 2
3 1 1 3 3
2 1 3 1 2
1 2 5
2 1 3 1 2
1 2 5
2 1 3 1 2

Output:
No
Yes
No
Yes

                               ANSWER