ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Winter 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Army of Mages

Time limit: 1.0 second
Memory limit: 64 MB
Everybody was silent. It became known that after the North battle all warriors of the great Coalition Army would stop defending their kingdom as battle mages and would serve as coaches. So it was the time to build a new powerful army. It was the wise Sandro who broke the silence and began to write down the names of the candidates. Finally, he wrote down 5n names. But only n best mages had to be chosen according to the law of the kingdom. After a long discussion it was decided to build an army in such a way that every two mages in this army would respect each other.
All mages in the kingdom live in their own houses, situated at the points on the plane with integer coordinates. Somewhy two mages respect each other if and only if a line segment connecting their houses contains at least one point with integer coordinates, different from endpoints of this segment. For example, if there are houses at points (1,1) and (5,5) then their inhabitants respect each other, because there is a point (2,2) on this segment. In the same time, inhabitants of the houses situated in (0,0) and (1,10) don't respect each other. Help the government to build an army!


The first line contains an integer n (1 ≤ n ≤ 5000). The i-th of the next 5n lines contains a pair of integers x and y, not exceeding 10000 by their absolute values—coordinates of the house of the i-th candidate. All houses are situated at different points.


If the required army can be built, output “OK” in the first line and in the second line output n space-separated numbers of the selected candidates in any order. If there are several possible answers, you can output any of them. If no army can be built, output “IMPOSSIBLE”.


1 1
5 5
0 0
2 2
0 10
6 6
7 7
8 8
9 9
10 10
2 1
Problem Author: Eugene Kurpilyanskiy
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009
To submit the solution for this problem go to the Problem set: 1690. Army of Mages