Transportation Network

Time Limit: 4 Seconds    Memory Limit: 32768 KB

A transportation network consists of a central node and some other nodes directly or indirectly (through some intermediate nodes) connected to the central node, and also the transporting channels which connect them. It is known that for any node in the transportation network there is exactly one path leads to the central. Every channel has its own length, the distance between any two nodes is defined as the total length their shortest path.

For example, in the following transportation network (the numbers in the parentheses represents the length of the channels):

      1
     /\
(2) /  \ (3)
   2    3
(2)|    |(2)
   |    |
   4    5

The distance between 2 and 3 is 5, the distance between 1 and 4 is 4, and the distance between 3 and 5 is 2.

Two transportation network can be combined, combining network A to network B means building a channel that connects the central of A and the central of B, and take the central of B as the central of the combined network. That combined network contains all the nodes and channels that is in network A or in network B.

Country-A has N (3 <= N <= 20,000) nodes that needs transporting between. Initially there is no channel between them, and each node is a solo transportation network. For the transporting the substance more expediently, Country-A has decided to build some transporting channels.

To maintain the information of the networks, Country-A has bought a super computer, which can receive and execute two kinds of instructions:

1) Q i j (1 <= i, j <= N, i <> j)

Querying the distance between node i and node j in the network. If they are not in the same network, output "Not connected." (Without quotation), output the distance otherwise.

2) U i j l (1 <= i, j <= N, node i and node j are not in the same network)

Combine the network containing i to the network containing j, makes the channel between them be l. (l is an integer, and 0 < l <= 1,000)
To avoid hackers' invasion which may cause the leak of the information, you should input the instruction U i' j' l instead of U i j l (where i' = (i + last_result) mod n + 1, j' = (j + last_result) mod n + 1 here last_result is the result of last valid query (i.e. the query that i and j are in the same network). Initially last_result = 0.

Your task is to write the program for the super computer.

Input

The first line of the input is an integer X (0 < X <= 6) represents number test cases of this problem. Then X blocks each represents
a test case.

The first line of each block contains two numbers N and M (5 <= M <= 40,000) representing country-A has N transportation nodes and the super computer will receive M instructions. Then M lines each represents an instruction, has the format Q i j or U i' j' l, which has been described above.

There're NO breakline between two continuous test cases.

Output

For each querying output one line an integer represents the distance or "Not connected." (Without quotation)

There're NO breakline between two continuous test cases.

Sample Input

2
4 6
U 3 4 4
Q 2 3
U 3 2 2
Q 1 2
U 2 3 1
Q 2 4
4 6
U 3 4 4
Q 2 3
U 3 2 2
Q 1 2
U 2 3 1
Q 2 4

Sample Output

4
6
7
4
6
7

Submit

Source: Online Contest of Christopher's Adventure