GTY likes playing games with ZZF. But ZZF doesn't like to play with GTY because GTY is too stupid. This time GTY invites ZZF to play games again! To avoid being laughed at by ZZF, this time GTY takes you, GTY's assistant in the game( Because you are muchsmarter than GTY). ZZF likes painting, so she drew a tree on the papar. It's so beautiful that GTY almost forgot he had a game to play... Then ZZF said, 'I could play this game with you, but you have to answer the question correctly and quickly. Or I will give you a good-man card. 'After that she drew some nodes on the tree, each of them having a value. During the game ZZF will ask you a question or let you do an operation :
$0~u~v$ : query the sum of the values of the nodes in the route$ (u, v)$
$1~u~v$ : reverse the values of the nodes in the route$ (u, v)$
For GTY doesn't want to be given a good-man card, he needs you to help him.
Input
In the first line there are two numbers n, the number of the nodes, and m, the number of the operations. ( $ 1 \leq n, m \leq 80000 $ )
The next line contains n numbers which are the values of the nodes. ( $ 1 \leq val_i \leq 1000 $ )
The next $n - 1$ lines describe the tree. In each line there are two numbers u and v, meaning there is an edge between u and v. ( $ 1 \leq u, v \leq n $ )
The next $m$ lines describe the queries and the operations. Each line contains three numbers $op, u, v$. Their meanings are the same as the description above.
