Religious Travel in S Country

S country has \(N\) cities numbered from \(1\) to \(N\). They are connected by \(N-1\) bidirectional roads forming a tree. Each city has its own religion represented by a positive integer and an individual travel rating. Residents often travel between cities following the shortest path. To avoid complications, a traveler only stays overnight in cities whose religion matches his own (which is the same as the starting city’s religion), and the journey’s destination is guaranteed to have the same religion as the starting city.

S country records the following types of events:

• CC x c: All residents of city \(x\) convert their religion to \(c\).
• CW x w: The travel rating of city \(x\) is updated to \(w\).
• QS x y: A traveler departs from city \(x\) and travels to city \(y\) along the unique shortest path. He only stays (including start and destination) in those cities whose religion equals that of city \(x\) at the time. He records the sum of the ratings of the cities where he stays.
• QM x y: Similar to QS except that the traveler records the maximum rating among the cities where he stays.

It is guaranteed that when a travel event occurs, the entire configuration (both religions and ratings) remains unchanged during that journey.

inputFormat

The input consists of several parts:

1. The first line contains two integers \(N\) and \(Q\) separated by a space, indicating the number of cities and the number of events.
2. The second line contains \(N\) integers. The \(i\)-th integer is the initial religion of city \(i\).
3. The third line contains \(N\) integers. The \(i\)-th integer is the initial travel rating of city \(i\).
4. Next, there are \(N-1\) lines, each containing two integers \(u\) and \(v\) indicating that there is a bidirectional road between cities \(u\) and \(v\).
5. Then follow \(Q\) lines, each representing an event in one of the following formats:
   CC x c
CW x w
QS x y
QM x y

outputFormat

For each event of type QS or QM, output a single line containing the result of that query.

sample

5 5
1 2 1 2 1
3 5 2 6 1
1 2
1 3
2 4
3 5
QS 1 4
QM 5 3
CC 2 1
CW 4 10
QS 1 4

3
2
8