Country S has $N$ cities, numbered from $1$ to $N$. The cities are connected by $N-1$ bidirectional roads, such that it is possible to reach any other city from any starting city. Each city follows a different religion, such as the Church of the Flying Spaghetti Monster, the Invisible Unicorn, or the Jedi. For convenience, we represent each religion with a distinct positive integer.

The residents of Country S travel frequently. When traveling, they always take the shortest path, and to avoid trouble, they only stay overnight in cities that share their religion. Naturally, the destination of the journey is also a city that shares their religion. The government of Country S has assigned a different travel rating to each city, and travelers often record the sum or the maximum of the ratings of the cities they stayed in (including the starting and ending cities).

The following types of events occur in the history of Country S:

• "CC $x$ $c$": All residents of city $x$ have converted to religion $c$;
• "CW $x$ $w$": The rating of city $x$ is adjusted to $w$;
• "QS $x$ $y$": A traveler starts from city $x$ and travels to city $y$, recording the sum of the ratings of the cities they stayed in;
• "QM $x$ $y$": A traveler starts from city $x$ and travels to city $y$, recording the maximum of the ratings of the cities they stayed in.

Due to the passage of time, the numbers recorded by the travelers have been lost, but the religion and rating of each city before the records began, as well as the event logs themselves, are intact. Please reconstruct the numbers recorded by the travelers based on this information.

For convenience, we assume that the intervals between events are long enough that the ratings and religions of all cities remain constant during any single journey.

Input

The first line contains two integers $N$ and $Q$, representing the number of cities and the number of events, respectively.

The next $N$ lines, the $i$-th line contains two integers $W_i, C_i$, representing the rating and religion of city $i$ before the records began.

The next $N-1$ lines each contain two integers $x, y$, representing a bidirectional road.

The next $Q$ lines each contain an operation, formatted as described above.

Output

For each QS and QM event, output one line representing the number recorded by the traveler.

Examples

Input 1

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

Output 1

8
9
11
3

Subtasks

In the table below, $C$ represents the total number of religions.

The data guarantees that for all QS and QM events, the starting and ending cities share the same religion; at any time, the rating of a city is a positive integer not exceeding $10^4$, and the religion value does not exceed $C$.