На собрании стояла довлеющая тишина. Стало окончательно ясно, что после битвы на Севере все члены великого войска Коалиции закончат карьеру боевых магов и займут руководящие должности Наставников. А значит, нужно срочно набирать новую боеспособную армию. Лишь мудрый Сандро нарушал тишину скрипом пера о бумагу — он выписывал имена достойных по его мнению кандидатов. Наконец, он закончил. На листке были написаны 5n имён. Но суровые законы предписывали выбрать лишь n достойнейших магов. После долгих споров, было решено создать армию, в которой каждая пара магов уважала бы друг друга.
Как известно, в королевстве все маги живут в отдельных домах, расположенных в точках плоскости с целыми координатами. Так получилось, что маги уважают друг друга в том и только в том случае, если на отрезке, соединяющем их дома, лежит хотя бы одна точка с целыми координатами, отличная от концов отрезка. Например, если дома расположены в точках (1,1) и (5,5), то эти маги уважают друг друга, так как между их домами есть точка (2,2). А вот жильцы домов с координатами (0,0) и (1,10), увы, не относятся друг к другу с уважением. Помогите правительству королевства собрать армию!
Исходные данные
В первой строке записано целое число n (1 ≤ n ≤ 5000).
В i-й из следующих 5n строк записана пара целых чисел x и y,
по модулю не превосходящих 10000 — координаты дома i-го кандидата в армию. Все дома расположены в различных точках.
Результат
Если искомая армия существует, в первой строке выведите «OK», а во второй строке запишите через пробел в произвольном порядке n чисел — номера выбранных кандидатов. Если возможных ответов несколько, выведите любой. Если армию создать нельзя, выведите «IMPOSSIBLE».
Пример
исходные данные | результат |
---|
2
1 1
5 5
0 0
2 2
0 10
6 6
7 7
8 8
9 9
10 10
| OK
2 1 |
Автор задачи: Евгений Курпилянский
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009