#P1871. 对撞机

对撞机

题目描述

在2312年,宇宙中发现了 nn 台巨型对撞机,这些对撞机分别用 1n1 \sim n 的自然数标识。科学家们不知道启动这些对撞机会发生什么危险事故,所以这些机器,刚开始都是出于关闭的状态。

随着科学家们的研究发现,第 ii 台对撞机启动是安全的,当且仅当其他已经启动的对撞机的标识数都跟这台对撞机标识数互质。(例如假设前面启动的对撞机标识数是 jj,如果 ii 能启动,那么 i,ji,j 互质,即 gcd(i,j)=1\gcd(i,j) = 1)。如果两台对撞机的标识数不为互质数就启动,那么就会发生爆炸事故。

基于前面的研究,科学家们准备做各种启动和关闭对撞机的实验。为了确保科学家们的生命安全,你要设计一个远程遥控的软件。

刚开始,所有的对撞机都是关闭状态。你的程序将会收到许多询问,格式为“启动、关闭第 ii 台对撞机”。这个程序应该能处理这些询问(根据收到询问的先后顺序处理)。程序按照如下的格式输出处理结果。

如果询问为 + i(表示启动第 ii 台对撞机),程序应该按照下面三种情况之一输出结果。

  • Success,表示启动第 ii 台是安全的。
  • Already on,表示第 ii 台在询问之前就已经启动了。
  • Conflict with j,表示第 ii 台与前面已经启动的第 jj 台冲突。如果前面有多台对撞机跟 ii 冲突,那么只输出其中任何一台即可。

如果询问为 - i(表示关闭第 ii 台对撞机),程序应该按照下面两种情况之一输出结果。

  • Success,表示关闭第 ii 台对撞机。

  • Already off,表示第 ii 台对撞机在询问之前就已经关闭了。

输入格式

第一行输入两个以空格隔开的整数 nnmm,分别表示对撞机的数量和询问数。

接下来 mm 行,表示询问,每行仅可能是 + i- i,表示开启或关闭第 ii 台对撞机。

输出格式

输出 mm 行,输出结果按照上面题目给定格式输出。

10 10 
+ 6
+ 10
+ 5
- 10
- 5
- 6
+ 10 
+ 3
+ 6
+ 3

Success
Conflict with 6
Success
Already off
Success
Success
Success
Success
Conflict with 3
Already on

提示

数据范围

1n,m1051 \le n,m \le 10^51in1 \le i \le n


感谢 @cn:苏卿念 提供 Special Judge