Задача №112588. Парк BlueTube
Как Вы уже поняли, дядя Паша любит гулять в парке BlueTube . Иногда случается, что во время прогулок людей похищают инопланетяне. К сожалению, именно это и случилось с нашим героем.
Инопланетяне попросили Пашу решить сложную задачу, оптимальное решение которой поможет им покорить мир. Задача была следующая: дан список из N натуральных чисел A i . Числа в списке нумеруются натуральными числами, начиная с единицы. Для каждого i нужно найти минимальное j ( j ≠ i ) такое, что dist ( A i , A j ) ≤ dist ( A i , A k ) для любого k ( 1 ≤ k ≤ N , k ≠ i ). Инопланетяне считают, что dist ( x , y ) — это минимальное количество операций, необходимых для того, чтобы из числа x получить число y . За одну операцию инопланетяне умеют умножать или делить число на любое простое число. Простым называется число, у которого ровно два различных делителя — единица и оно само. Например, dist (10, 24) = 4 .
Паша испугался, поэтому сразу позвонил Роме. Как Вы уже догадались, Рома — так себе программист, но помимо этого он еще и увлекся решением примеров по математическому анализу. Рома дал Паше Ваш номер, поэтому только Вы можете спасти нашего героя! Решите поставленную задачу, чтобы Паша мог вернуться обратно в BlueTube .
В первой строке входного файла содержится число N ( 2 ≤ N ≤ 10 5 ) — количество чисел в списке.
В следующих N строках входного файла последовательно заданы числа A i (1 ≤ A i ≤ 10 6 ) по одному в строке, начиная с A 1 .
Выведите N чисел, по одному в строке. В строке номер i должен быть искомый индекс j для этого i .
Тесты к этой задаче состоят из двух групп:
-
Первая группа тестов состоит из тестов, для которых выполняется ограничение
N
≤ 1000
. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет
30
баллов.
- Вторая группа тестов состоит из тестов, для которых выполняется ограничение N ≤ 10 5 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 70 баллов.
6 1 2 3 4 5 6
2 1 1 2 1 2