Once upon a time, there was a coder named Andy who worked as the problem coordinator at the Canadian Computing Olympiad (CCO). The CCO is modeled after the IOI, and there are 2 days with 3 problems each.
Day 1 of the competition was over. Unexpectedly, all of the competitors had gotten perfect scores. Shocked at the young programming talent of the country, the organizing committee held an emergency meeting. They must make the Day 2 problems harder!
Not long after the meeting started, an argument started between two of the problem setters. They were fighting over whose problem should be used for the easiest task of Day 2.
The first problem setter said: "We should ask the competitors to solve some queries for the sum on paths of a tree!"
The second problem setter said: "That's way too easy! Clearly, a problem about reversing subarrays in an array and printing some elements of the final array is the way to go!"
Frustrated, the two problem setters turned to Andy to seek his opinion. Andy thought about it for a while, and came up with the perfect solution:
"Why not both?"
The two problem setters immediately realized the wisdom of these words and bowed down in respect to Andy. Andy quickly typed up the new statement:
There is a tree with N vertices. Initially, each vertex has an integer value associated with it. You are given Q queries. Each query is either in the form R u v or S u v.
A query of the form R u v means you should reverse the order of all the values on the path between vertices u and v.
A query of the form S u v means you should output the sum of all the values on the path between vertices u and v.
Andy immediately starts working on the author's solution. Meanwhile, the two problem setters realize that they have no idea how to solve this problem. They decided to look on HackerEarth to find someone to write a tester's solution for them. Can you help them?
Input Format:
The first line of input will contain N and Q, the number of vertices and the number of queries, respectively.
The second line of input will contain N integers A1 to AN. Vertex i is initially associated with the value Ai.
The next N - 1 lines will contain the edges of the tree. Each line contains a pair of integers, and the corresponding vertices are connected by an edge. It is guaranteed that the list of edges will form a tree.
The next Q lines will each contain a query, either in the form R u v or S u v.
Output Format:
For each query in the form S u v, you should output the answer on its own line.
Constraints:
For all subtasks,
1 ≤ u, v ≤ N
1 ≤ Ai ≤ 104
[Subtask 1 - 11%]
2 ≤ N ≤ 105
1 ≤ Q ≤ 2 × 105
Additionally, there will be no queries in the form R x y. Note that this subtask corresponds to the task proposed by the first problem setter.
[Subtask 2 - 16%]
2 ≤ N ≤ 105
1 ≤ Q ≤ 2 × 105
Additionally, each vertex i in the tree will only be connected to vertices i - 1 and i + 1, if they exist (so the "tree" looks like an array). There will be at most 10 queries in the form S i i (sum of a single element), and these will come after all reversal queries. Note that this subtask corresponds to the task proposed by the second problem setter.
[Subtask 3 - 18%]
2 ≤ N ≤ 5000
1 ≤ Q ≤ 5000
[Subtask 4 - 55%]
2 ≤ N ≤ 105
1 ≤ Q ≤ 2 × 105