Giải bài trực tuyến

"A Long Time Ago, in a Galaxy Far, Far Away..." one advanced civilization discovered a manner of instant traveling between solar systems. Since that moment, they have devoted all their efforts to constructing pairs of stargates that connect distant planets. Soon enough communication network became so complex that they require help to maintain information about the connected worlds.

Write a program that will help them maintain information about the connected systems and we will make sure that the best of your solutions will be forwarded to their space-time continuum.

Planets A and B are connected if there is a direct stargate connection between them, or there is a planet sequence P1, P2 ... Pn where P1 = A, Pn = B and there is a direct stargate connection between Pk and Pk-1, k ∈ {2,..n}.

Connections are bidirectional. There can be multiple connection paths between two planets.

Input

Input file consist of multiple data sets. Each data set occupies one or more lines. There are no empty lines in the input file. Each line starts with a single letter ‘D’, ‘C’ or ‘Q’ (upper or lower case) followed by 1 to 5 integers with following meaning:

• ‘D’ (define) has only one argument which defines number of planets N considered in following data set (N <= 6000000, planets are numbered from 1 to N).
• ‘C’ (connect) creates a connection between a given pair(s) of planets.
• ‘Q’ (query) examines if a given pair(s) of planets are connected.

Both ‘C’ and ‘Q’ command (‘X’ in following text) share the same syntax:

X src dst – Creates a connection (or query) between given pair of planets (src, dst).

X src dst nnn – Creates a connection (or query) between src planet and nnn consecutive planets numerated from dst.

Example: C 1 100 3 creates following links (1,100), (1,101), (1,102).

X src dst nnn step – Creates a connection (or query) between src planet and nnn planets numerated from dst with given step.

Example: C 1 100 3 5 creates following links (1,100), (1,105), (1,110).

X src dst nnn dststep srcstep – Creates a connection (or query) between nnn pairs of planets numerated from src with srcstep and dst with dststep respectively.

Example: C 1 100 3 5 15 creates following links (1,100), (16,105), (31,110).

Output

Output should contain one line for each query (‘Q’) line in the input file. Each line contains two numbers separated by a space. First value represents number of connected planet pairs from appropriate query while second represents number of disconnected planet pairs.

Sample

Input:
d 5
C 1 3
D 20
q 1 3
c 1 10 10
Q 1 2 18 1 1

Output:
0 1
9 9

Input:
d 5
d 1
q 1 1
d 10
q 1 6 5 1 1
c 1 2 9
q 1 6 5 1 1

Output:
1 0
0 5
5 0

Notice : ‘D’, ‘C’ or ‘Q’ can be upper or lower case.