B. Коллайдеры
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

К 2312 году в обитаемой части Вселенной насчитывалось уже n Больших Адронных Коллайдеров, каждому из которых сопоставлялось уникальное натуральное число от 1 до n. Однако ученые не знали, к чему могло привести одновременное включение нескольких коллайдеров, поэтому они так и стояли в выключенном состоянии.

В 2312 году произошло потрясающее открытие: работа коллайдеров безопасна тогда и только тогда, когда все номера включенных коллайдеров попарно взаимно просты друг с другом (два числа взаимно просты, если их наибольший общий делитель равен 1)! Если одновременно будут включены два коллайдера со взаимно непростыми номерами, произойдет глобальный коллапс.

Узнав это, физики тут же бросились включать-выключать коллайдеры и ставить на них разные эксперименты. Чтобы из-за расторопности ученых не произошло беды, был создан Большой Пульт Управления Большими Адронными Коллайдерами. Программное обеспечение для него было поручено написать Вам (ну не вручную же им управлять?).

Изначально все коллайдеры находятся в выключенном состоянии. Вашей программе поступает множество запросов вида «включить/выключить i-ый коллайдер». Программа должна обрабатывать запросы в порядке их поступления и выводить результаты обработки в формате, описанном ниже.

На запрос «+ i» (то есть включить i-ый коллайдер), программа должна выводить ровно один из следующих ответов:

  • «Success», если включение прошло успешно.
  • «Already on», если до запроса i-ый коллайдер уже был включен.
  • «Conflict with j», если происходит конфликт с j-ым коллайдером (то есть j-ый коллайдер включен, и числа i и j не взаимно просты). В этом случае i-ый коллайдер включать не нужно. Если конфликт происходит сразу с несколькими коллайдерами, можно вывести номер любого из них.

На запрос «- i» (то есть выключить i-ый коллайдер), программа должна выводить ровно один из следующих ответов:

  • «Success», если выключение прошло успешно.
  • «Already off», если до запроса i-ый коллайдер уже был выключен.

При выводе ответа на запрос кавычки выводить не нужно.

Входные данные

В первой строке записано два целых числа, разделенных пробелом — n и m (1 ≤ n, m ≤ 105) — количество коллайдеров и количество запросов соответственно.

В следующих m строках даны описания запросов, по одному запросу в строке в формате «+ i» (без кавычек) — включить i-ый коллайдер, либо «- i» (без кавычек) — выключить i-ый коллайдер (1 ≤ i ≤ n).

Выходные данные

Выведите m строк — результаты выполнения запросов в формате, описанном выше. Запросы необходимо обрабатывать в том порядке, в котором они подаются на вход. Не забудьте, что ответы на запросы требуется выводить без кавычек.

Примеры
Входные данные
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 10
Already on
Примечание

Обратите внимание, что в примере после второго и девятого запросов включения не происходит. На девятый запрос допустимо также вывести «Conflict with 3».