시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB55924717546.543%

문제

지구에서 보낸 화성표면 탐사로봇은 2032년 현재 100개 이상이고, 그 개수가 빠르게 증가하고있다. 그 이유는 지구에는 없는 귀중한 금속 자원이 화성표면에서 속 속 발견되고 있기 때문이다.

화성 궤도에는 모선이 돌고 있어서, 화성 표면에서 임무를 수행하는 수많은 로봇과 수시로 데이타와 명령을 주고 받도록 되어있다.

이 모선이 하는 일 중 하나는 화성 대기에 먼지 폭풍이 예상되었을 때, 표면 탐사 로봇을 대피소로 대피시키는 것이다. 모선에서는 화성 표면의 로봇에게 대피해야 할 대피소를 지정해주고 대피 명령을 내리는 것이다.

하나의 대피소에는 하나의 로봇만 수용할 수 있고, 대피 명령을 받은 로봇은 직선경로로 대피소를 향해 전속력으로 이동하게 되어있다. 문제는 로봇이 대피소로 이동중에 다른 로봇과 충돌할 수 있다는 점이다. 충돌할 일이 없도록 각각의 로봇에게 대피소를 할당해 주는 프로그램을 작성하라.

화성은 2차원 평면이다. 위도와 경도는 왼쪽 위를 (0,0)으로 오른쪽 아래는 (100,100)으로 한다.

입력

첫째 줄에 로봇과 대피소의 수 N (1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 로봇의 위도와 경도가 1번 로봇부터 N번 로봇까지 한 줄에 하나씩 주어진다. 다음 N개의 줄에 대피소의 위도와 경도가 1번 대피소부터 N번 대피소까지 한 줄에 하나씩 주어진다.

로봇과 대피소의 위치가 같은 경우는 없으며, 로봇과 대피소는 항상 화성 표면 위에 있다.

출력

i번 로봇이 대피할 대피소의 번호를 i번 줄에 출력한다.

항상 모든 로봇이 대피할 수 있는 경우만 입력으로 주어진다. 가능한 답이 여러가지인 경우에는 아무거나 출력한다.

예제 입력 1

2
1 1
1 99
99 99
99 1

예제 출력 1

2
1

예제 입력 2

4
3 2
2 9
3 0
4 2
88 3
12 9
100 0
4 3

예제 출력 2

4
2
3
1