P1871 Collider

In the year 2312, $n$ giant colliders were discovered in the universe, labeled by the natural numbers $1 \sim n$. Scientists do not know what dangerous accidents might occur when these colliders are turned on, so at the beginning all the machines are in the off state. Through research, scientists found that turning on collider $i$ is safe if and only if the labels of all colliders that are already on are coprime with the label of collider $i$. (For example, suppose a previously turned on collider has label $j$, then if $i$ can be turned on, $i$ and $j$ are coprime, that is, $\gcd(i,j) = 1$.) If two colliders with labels that are not coprime are turned on, an explosion will occur. Based on the above, scientists plan to run various experiments of turning colliders on and off. To ensure their safety, you need to design remote-control software. Initially, all colliders are off. Your program will receive many queries of the form “turn on or turn off collider $i$.” The program should process these queries in the order they are received and output results in the following format. If a query is `+ i` (turn on collider $i$), the program should output exactly one of the following: - `Success`, meaning that turning on collider $i$ is safe. - `Already on`, meaning collider $i$ was already on before this query. - `Conflict with j`, meaning collider $i$ conflicts with some collider $j$ that is already on. If multiple colliders conflict with $i$, output any one of them. If a query is `- i` (turn off collider $i$), the program should output exactly one of the following: - `Success`, meaning collider $i$ has been turned off. - `Already off`, meaning collider $i$ was already off before this query.

The first line contains two space-separated integers $n$ and $m$, the number of colliders and the number of queries. The next $m$ lines are the queries. Each line is either `+ i` or `- i`, meaning to turn on or turn off collider $i$.

Output $m$ lines. For each query, output the result in the format specified above.

Constraints $1 \le n,m \le 10^5$, $1 \le i \le n$. --- Thanks to @cn: 苏卿念 for providing the Special Judge. Translated by ChatGPT 5