Stargates

Long ago, in a distant galaxy, an advanced civilization discovered instant travel between solar systems and began building pairs of stargates that link far-apart planets. Their network grew so complex that they need help tracking which worlds are connected.

Write a program that maintains connectivity information about the systems. Two planets $A$ and $B$ are connected if there is a direct stargate between them, or if there is a sequence of planets $P_1, P_2, \ldots, P_n$ with $P_1 = A$ and $P_n = B$ such that $P_{k-1}$ and $P_k$ are directly connected for every $k \in {2, \ldots, n}$. All connections are bidirectional, and there may be several paths between two planets.

The input consists of one or more data sets and contains no blank lines. Each command is on its own line and starts with a single letter — 'D', 'C', or 'Q' (upper or lower case) — followed by $1$ to $5$ integers:

• 'D' (define) takes one integer $N$ ($N \le 6000000$): it starts a new data set with planets numbered $1$ to $N$ and no connections.
• 'C' (connect) adds stargate connections between one or more pairs of planets.
• 'Q' (query) asks whether one or more pairs of planets are connected.

The 'C' and 'Q' commands (written 'X' below) share the same argument syntax:

• X src dst — one pair $(src, dst)$.
• X src dst nnn — the $nnn$ pairs $(src, dst), (src, dst+1), \ldots, (src, dst+nnn-1)$. For example, X 1 100 3 refers to $(1,100), (1,101), (1,102)$.
• X src dst nnn step — the $nnn$ pairs $(src, dst + i \cdot step)$ for $i = 0, \ldots, nnn-1$. For example, X 1 100 3 5 refers to $(1,100), (1,105), (1,110)$.
• X src dst nnn dststep srcstep — the $nnn$ pairs $(src + i \cdot srcstep, dst + i \cdot dststep)$ for $i = 0, \ldots, nnn-1$. For example, X 1 100 3 5 15 refers to $(1,100), (16,105), (31,110)$.

For a 'C' command every listed pair is connected; for a 'Q' command every listed pair is tested. All referenced planet numbers lie between $1$ and the current $N$.

Print one line for every 'Q' (query) command, in order. Each line contains two integers separated by the three-character sequence ' - ' (a space, a hyphen-minus, and a space): first the number of pairs in that query that are connected, then the number of pairs that are not connected. Do not print any trailing spaces.