역사 전시회
시간 제한1초메모리 제한512 MB
각 꽃병을 받침대의 위나 아래 지름이 꽃병 밑면과 일치하도록 서로 다른 받침대에 배정하고, 필요하면 받침대를 뒤집으며 불가능하면 impossible을 출력한다.
문제
베네룩스 예술 도자기 컨소시엄이 가장 귀중한 항아리와 꽃병을 네이메헌의 한 갤러리에서 전시할 준비를 하고 있다. 전시할 꽃병의 수가 너무 많아 갤러리 측은 모든 꽃병에 맞는 크기의 받침대를 찾는 데 어려움을 겪고 있다. 갤러리에는 똑바로 놓거나 뒤집어 놓을 수 있는 받침대가 있으며, 각 받침대는 윗면과 아랫면의 지름으로 특징지을 수 있다. 또한 윗면과 아랫면의 지름 차이는 최대 1 단위 길이이다.
예술적인 이유로 꽃병의 밑면 지름은 꽃병을 올려놓는 받침대 면의 지름과 일치해야 한다. 갤러리 측은 모든 꽃병을 사용 가능한 받침대 위에 놓는 방법을 찾아 달라고 요청했다. 이렇게 하려면 받침대 일부를 뒤집어야 할 수도 있다. 예를 들어 그림 H.1은 예제 입력 1에 대한 받침대 배치 중 하나를 보여준다. 이러한 배치를 계산하는 프로그램을 작성해 갤러리를 도와라.
그림 H.1: 예제 입력 1의 해.
입력
- 첫째 줄에는 받침대의 수와 꽃병의 수를 나타내는 두 정수 0 ≤ p, v ≤ 104가 주어진다.
- 다음 p개 줄 중 i번째 줄에는 받침대 i의 양면 지름을 나타내는 두 정수 1 ≤ ai, bi ≤ 104가 주어진다. |ai − bi| ≤ 1이 보장된다.
- 다음 한 줄에는 v개의 정수 1 ≤ c1, . . . , cv ≤ 104가 주어지며, ci는 꽃병 i의 지름이다.
출력
- 꽃병 i를 받침대 xi 위에 놓을 수 있도록 하는 v개의 서로 다른 정수 1 ≤ x1, . . . , xv ≤ p를 출력하거나, 꽃병을 받침대에 배치하는 방법이 없으면 impossible을 출력한다.
가능한 해가 여러 개라면 그중 아무거나 출력해도 된다.