Legend of the Galactic Heroes

In the year 5801, Earth's residents migrated to the second planet of the Taurus constellation $\alpha$, where they declared the founding of the Galactic Federation. That same year was designated as Year 1 of the Cosmic Era, and expansion into the depths of the galaxy began.

In the year 799 of the Cosmic Era, two major military groups in the galaxy clashed in the Vermilion Star Zone. The "Taishan Yading" group, led by fleet commander Reinhard, dispatched over 100,000 warships, while the "Qintun Shanhe" group, led by Yang Wen-li, organized 30,000 warships to meet the enemy.

Yang Wen-li is skilled in tactical deployment and has repeatedly used various tactics to defeat larger forces with smaller ones, which inevitably leads to a bit of arrogance. In this decisive battle, he divided the Vermilion Star Zone into 30,000 columns, numbered 1, 2, ..., 30,000. He then numbered his own warships 1, 2, ..., 30,000, placing warship $i$ in column $i$ ($i = 1, 2, \dots, 30,000$), forming a "long snake formation" to lure the enemy deep. This is the initial formation. When the invading enemy arrives, Yang Wen-li issues multiple merge commands to concentrate most of his warships into a few columns for a concentrated attack. A merge command is given as $M\ i\ j$, which means to take the entire warship queue containing warship $i$ and attach it as a whole (head first, tail last) to the end of the warship queue containing warship $j$. Clearly, a warship queue consists of one or more warships in the same column. The execution of a merge command increases the size of the queue.

However, the cunning Reinhard had already gained the strategic initiative. During the battle, he could monitor Yang Wen-li's fleet movement commands at any time through a massive intelligence network.

While Yang Wen-li issues commands to move his fleet, Reinhard also issues some inquiry commands to keep track of the current distribution of Yang Wen-li's warships: $C\ i\ j$. This command means to ask the computer whether warship $i$ and warship $j$ are currently in the same column, and if they are, how many warships are positioned between them.

As a senior programmer, you are required to write a program to analyze Yang Wen-li's commands and answer Reinhard's inquiries.

The final battle has begun, and another page of galactic history has been turned...

Input

The first line of the input contains an integer $T$ ($1 \le T \le 500,000$), representing the total number of commands.

The following $T$ lines each contain one command. There are two types of commands:

1. $M\ i\ j$: $i$ and $j$ are two integers ($1 \le i, j \le 30,000$), representing the warship numbers involved in the command. This command is a fleet movement command issued by Yang Wen-li and intercepted by Reinhard. It is guaranteed that warship $i$ and warship $j$ are not in the same column.
2. $C\ i\ j$: $i$ and $j$ are two integers ($1 \le i, j \le 30,000$), representing the warship numbers involved in the command. This command is an inquiry command issued by Reinhard.

Output

Your program should analyze and process each input command in order:

If it is a fleet movement command issued by Yang Wen-li, it means the fleet arrangement has changed. Your program should note this, but do not output any information.

If it is an inquiry command issued by Reinhard, your program should output a single line containing one integer, representing the number of warships positioned between warship $i$ and warship $j$ in the same column. If warship $i$ and warship $j$ are not currently in the same column, output $-1$.

Examples

Input 1

4
M 2 3
C 1 2
M 2 4
C 4 2

Output 1

-1
1

Note

Warship position diagram: The Arabic numerals in the table represent warship numbers.