Chef and Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
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 A_{v} associated with it. Queries can be one of three types.
 1 u v  reverse the values on the path between vertices u and v.
 2 u_{l} u_{r} v_{l} v_{r}  print "Yes" if all the values on the path from u_{l} to u_{r} are exactly same as that of path from v_{l} to v_{r}, and "No" otherwise. It is ensured that length of both the paths are same.
 3 u_{l} u_{r} v_{l} v_{r}  Copy all values on path from u_{l} to u_{r} and insert them into the path from v_{l} to v_{r}. 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 spacesepareted integers denoting A_{v}  the values associated with nodes.
Next N1 lines contains two spacesepareted integers u, v denoting the nodes connected by an edge.
Next Q lines contains queries as described above.
Output
For each query of second type output your answer in a single line.
Constraints
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{3}
 1 ≤ u, v, u_{l}, u_{r}, v_{l}, v_{r} ≤ 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
Author:  mgch 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CHEFTRE 
Tags  aug16, decomposition, hard, heavylight, mgch, segmenttree 
Date Added:  13072016 
Time Limit:  9 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 