У Аркадия есть плейлист, в котором изначально \(n\) песен, пронумерованных от \(1\) до \(n\) в том порядке, в котором они находятся в плейлисте. Аркадий начинает слушать песни из плейлиста друг за другом, начиная с песни \(1\). Плейлист зациклен, то есть после того, как он прослушает последнюю песню, он опять начнет слушать с начала плейлиста.
У каждой песни есть жанр, определяемый натуральным числом \(a_i\). Пусть Аркадий только что прослушал песню с жанром \(y\), а до нее — песню с жанром \(x\). Если \(\operatorname{gcd}(x, y) = 1\), он думает, что песни не сочетаются, и удаляет последнюю прослушанную песню (с жанром \(y\)) из плейлиста. После этого он продолжает слушать песни как обычно, пропуская уже удаленные, при этом он забывает, что слушал какие-то песни до удаления. Иными словами, он не может удалить песню сразу после того, как удалил предыдущую. Здесь \(\operatorname{gcd}(x, y)\) обозначает наибольший общий делитель (НОД) чисел \(x\) и \(y\).
Например, если жанры песен в начальном плейлисте равны \([5, 9, 2, 10, 15]\), то прослушивание происходит следующим образом: [5, 9, 2, 10, 15] \(\to\) [5, 9, 2, 10, 15] \(\to\) [5, 2, 10, 15] (т. к. \(\operatorname{gcd}(5, 9) = 1\)) \(\to\) [5, 2, 10, 15] \(\to\) [5, 2, 10, 15] \(\to\) [5, 2, 10, 15] \(\to\) [5, 2, 10, 15] \(\to\) [5, 2, 10, 15] \(\to\) [5, 10, 15] (т. к. \(\operatorname{gcd}(5, 2) = 1\)) \(\to\) [5, 10, 15] \(\to\) [5, 10, 15] \(\to\) ... Жирным выделены последние две прослушанные песни. Обратите внимание, после удаления некоторой песни Аркадий забывает, что слушал ее и предыдущую.
Вам дан начальный плейлист, определите, какие песни будут в итоге удалены и в каком порядке.
Выходные данные
Для каждого набора входных данных выведите одну строку. Сначала выведите одно целое число \(k\) — количество песен, которые будут удалены. Затем выведите \(k\) различных целых чисел — номера удаленных песен в порядке удаления.
Примечание
Первый набор входных данных объяснен в условии.
Во втором наборе плейлист изменяется следующим образом: [1, 2, 4, 2, 4, 2] \(\to\) [1, 2, 4, 2, 4, 2] \(\to\) [1, 4, 2, 4, 2] (т. к. \(\operatorname{gcd}(1, 2) = 1\)) \(\to\) [1, 4, 2, 4, 2] \(\to\) [1, 4, 2, 4, 2] \(\to\) [1, 4, 2, 4, 2] \(\to\) [1, 4, 2, 4, 2] \(\to\) [1, 4, 2, 4, 2] \(\to\) [4, 2, 4, 2] (т. к. \(\operatorname{gcd}(2, 1) = 1\)) \(\to\) [4, 2, 4, 2] \(\to\) ...
Во третьем наборе плейлист изменяется следующим образом: [1, 2] \(\to\) [1, 2] \(\to\) [1] (т. к. \(\operatorname{gcd}(1, 2) = 1\)) \(\to\) [1] \(\to\) [1] (Аркадий послушал одну и ту же песню подряд дважды) \(\to\) [] (т. к. \(\operatorname{gcd}(1, 1) = 1\)).
Четвертый набор входных данных совпадает с предыдущим после удаления второй песни.
В пятом примере Аркадий слушает одну и ту же песню снова и снова, но т. к. \(\operatorname{gcd}(2, 2) \ne 1\), он не удаляет ее.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
5 9 2 10 15
6
1 2 4 2 4 2
2
1 2
1
1
1
2
|
2 2 3
2 2 1
2 2 1
1 1
0
|