In the Pokémon Ruby/Sapphire/Emerald water-type gym, one must traverse three ice floors to reach the gym leader. Each ice block on an ice floor can be stepped on only once. Only after all ice blocks on one floor have been traversed will the stairs to the next ice floor open. The three ice floors are as follows:

First Pool

Second Pool

Third Pool

After exiting the third ice floor, one can battle the gym leader. The gym leader found this too easy, as challengers were passing too frequently. To increase the difficulty, the gym was divided into $n$ rooms, where each room contains two ice blocks or obstacles, representing a column of ice. There is exactly one path between any two rooms, meaning the $n$ rooms form a tree structure. Each room is divided into two areas, $A$ and $B$, each of which is either a thin ice block or an obstacle. You can only move to the same type of area in an adjacent room (i.e., if you are currently in area $A$ of a room, you can only move to area $A$ of an adjacent room) or to the other area within the same room. Now, a challenger starts at room $u$, and the gym leader is in room $v$; the challenger must move in the direction towards the room where the gym leader is located. Initially, the challenger can be in any ice block area of room $u$. If the number of ice blocks the challenger has stepped on reaches the maximum possible value (i.e., there is no other path that allows stepping on more ice blocks), then upon stepping on the last ice block, they will be instantly teleported to the gym leader to begin the battle. Since the gym leader modified the rules, $m$ days have passed. Each day, either a challenger arrives, or the gym leader modifies a room. For each challenger, you need to calculate the number of ice blocks they must traverse to battle the gym leader.

Input

The first line contains two positive integers $n$ and $m$. The next $n-1$ lines each contain two positive integers $x$ and $y$, representing an edge connecting room $x$ and room $y$. The rooms are numbered $1 \ldots n$. The next $n$ lines each contain two characters. The $(n+k)$-th line represents the two areas of room $k$, where the first character is area $A$ and the second is area $B$. "." represents a thin ice block, and "#" represents an obstacle. The final $m$ lines each contain an operation:

• C u s: Modify the two areas in room $u$ to the string s (length 2, consisting of "." or "#").
• Q u v: Query the number of ice blocks the challenger must step on to battle the gym leader, given the challenger is in room $u$ and the leader is in room $v$. If both areas in room $u$ are obstacles, output 0.

Output

Contains several lines, each containing an integer. Output the answer for each query in the input sequentially.

Examples

Input 1

5 3
1 2
2 3
2 4
1 5
.#
..
#.
.#
..
Q 5 3
C 1 ##
Q 4 5

Output 1

6
3

Note 1

For the first query, the path with the maximum number of ice blocks starting from room 5 is:

For the second query, the path with the maximum number of ice blocks starting from room 4 is:

Constraints