CF154B.Colliders

By 2312 there were n Large Hadron Colliders in the inhabited part of the universe. Each of them corresponded to a single natural number from 1 to n. However, scientists did not know what activating several colliders simultaneously could cause, so the colliders were deactivated.

In 2312 there was a startling discovery: a collider's activity is safe if and only if all numbers of activated colliders are pairwise relatively prime to each other (two numbers are relatively prime if their greatest common divisor equals 1)! If two colliders with relatively nonprime numbers are activated, it will cause a global collapse.

Upon learning this, physicists rushed to turn the colliders on and off and carry out all sorts of experiments. To make sure than the scientists' quickness doesn't end with big trouble, the Large Hadron Colliders' Large Remote Control was created. You are commissioned to write the software for the remote (well, you do not expect anybody to operate it manually, do you?).

Initially, all colliders are deactivated. Your program receives multiple requests of the form "activate/deactivate the i-th collider". The program should handle requests in the order of receiving them. The program should print the processed results in the format described below.

To the request of "+ i" (that is, to activate the i-th collider), the program should print exactly one of the following responses:

• "Success" if the activation was successful.
• "Already on", if the i-th collider was already activated before the request.
• "Conflict with j", if there is a conflict with the j-th collider (that is, the j-th collider is on, and numbers i and j are not relatively prime). In this case, the i-th collider shouldn't be activated. If a conflict occurs with several colliders simultaneously, you should print the number of any of them.

The request of "- i" (that is, to deactivate the i-th collider), should receive one of the following responses from the program:

• "Success", if the deactivation was successful.
• "Already off", if the i-th collider was already deactivated before the request.

You don't need to print quotes in the output of the responses to the requests.

到2312年，人类居住的宇宙区域内共建有 $n$ 台大型强子对撞机（Large Hadron Colliders）。每台对撞机对应一个从 $1$ 到 $n$ 的唯一自然数。然而，科学家尚不清楚同时启动多台对撞机会引发何种后果，因此所有对撞机均处于关闭状态。

2312年，一项惊人发现问世：当且仅当所有已启动对撞机所对应的编号两两互质时，对撞机的运行才是安全的（两个数互质，当且仅当它们的最大公约数为 $1$）！若启动两台编号不互质的对撞机，则将引发全球性崩溃。

得知这一规律后，物理学家们迅速开始反复启停对撞机，并开展各类实验。为防止科学家们的操作过快而酿成大祸，“大型强子对撞机远程集中控制系统”应运而生。你被委任为此远程控制系统编写软件（嗯，你总不会指望有人手动操作它吧？）

初始状态下，所有对撞机均处于关闭状态。你的程序将接收若干条形如“启动/关闭第 $i$ 台对撞机”的请求，并按接收顺序依次处理这些请求。程序需按如下格式输出每条请求的处理结果。

对于请求 “+ i”（即启动第 $i$ 台对撞机），程序应恰好输出以下响应之一：

• “Success”，表示启动成功；
• “Already on”，表示第 $i$ 台对撞机在收到该请求前已处于启动状态；
• “Conflict with j”，表示与第 $j$ 台对撞机发生冲突（即第 $j$ 台对撞机当前处于启动状态，且 $i$ 与 $j$ 不互质）。此时，第 $i$ 台对撞机不得启动。若同时与多个已启动对撞机发生冲突，则可输出其中任意一个冲突对撞机的编号 $j$。

对于请求 “- i”（即关闭第 $i$ 台对撞机），程序应输出以下响应之一：

• “Success”，表示关闭成功；
• “Already off”，表示第 $i$ 台对撞机在收到该请求前已处于关闭状态。

注意：输出响应内容时不得包含引号。

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the number of colliders and the number of requests, correspondingly.

Next m lines contain numbers of requests, one per line, in the form of either "+ i" (without the quotes) — activate the i-th collider, or "- i" (without the quotes) — deactivate the i-th collider (1 ≤ i ≤ n).

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \le n, m \le 10^5$），分别表示对撞机的数量和请求的数量。

接下来的 $m$ 行每行包含一个请求，格式为：“+ i”（不含引号），表示启动第 $i$ 台对撞机；或 “- i”（不含引号），表示关闭第 $i$ 台对撞机（其中 $1 \le i \le n$）。

Print m lines — the results of executing requests in the above given format. The requests should be processed in the order, in which they are given in the input. Don't forget that the responses to the requests should be printed without quotes.

输出 m 行——按上述格式执行请求的结果。请求应按照输入中给出的顺序进行处理。注意：请求的响应需不带引号输出。

Note that in the sample the colliders don't turn on after the second and ninth requests. The ninth request could also receive response "Conflict with 3".

注意，在样例中，碰撞检测器在第二次和第九次请求后并未启动。第九次请求的响应也可能是“与 3 冲突”。