기말고사

알고리즘과 자료구조 기말고사를 볼 시간이다!

Edsger는 N개의 문제 세트를 준비했다. 각 세트는 난이도가 증가하는 순서로 된 문제들로 이루어져 있다. i번째 세트는 두 정수 Ai와 Bi (Ai ≤ Bi)로 나타낼 수 있고, 이 세트에는 난이도가 Ai, Ai+1, …, Bi인 문제들이 들어 있다. 모든 세트의 문제 가운데 난이도가 같은 두 문제는 없다.

이번 학기에 Edsger는 M명의 학생을 시험해야 한다. 그는 각 학생에게 자신의 세트 중 하나에서 정확히 한 문제를 내려고 한다. 두 학생이 똑같은 문제를 받을 수는 없으므로, Edsger가 어떤 문제로 학생을 시험하면 그 문제는 더 이상 쓸 수 없다. 수많은 강의와 연습, 프로젝트를 거치면서 Edsger는 j번째 학생의 실력을 Sj로 측정했고, 그 학생에게 난이도 Sj인 문제를 내고 싶어 한다. 하지만 항상 가능한 것은 아니다. Edsger가 그 난이도의 문제를 준비하지 않았을 수도 있고, 그 문제를 이미 다른 학생에게 냈을 수도 있다. 따라서 Edsger는 j번째 학생에게 난이도 Pj인 문제를 고르되, |Pj−Sj|가 최소가 되고 난이도 Pj인 문제가 j번째 학생보다 앞선 학생에게 주어지지 않은 것으로 고른다. 차이가 같은 문제가 여럿이면 Edsger는 항상 더 쉬운 문제를 고른다. j번째 학생에게 고른 문제는 그 뒤에 시험하는 모든 학생에게 고를 문제에 영향을 줄 수 있으므로, 학생들을 입력에 나온 순서대로 처리해야 한다.

모든 문제를 관리하는 일은 꽤 복잡할 수 있다. Edsger를 도와 모든 학생에게 어떤 문제를 내야 하는지 구해 줄 수 있는가?

첫째 줄에 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 N과 M이 주어진다. N은 문제 세트의 수, M은 학생의 수이다. 그다음 N개의 줄에 문제 세트가 주어진다. 이 N개의 줄은 각각 두 정수 Ai와 Bi를 포함하며, i번째 문제 세트에서 가장 쉬운 문제와 가장 어려운 문제의 난이도를 나타낸다. 마지막으로 테스트 케이스는 M개의 정수 S1, S2, …, SM이 주어지는 한 줄로 끝난다. 이는 시험을 볼 순서대로 나열한 학생들의 실력이다.

각 테스트 케이스마다 Case #x: P1P2…PM 형식의 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, Pj는 j번째 학생에게 낼 문제의 난이도이다.

• 1 ≤ T ≤ 100.
• 모든 문제 세트에서 난이도가 같은 두 문제는 없다.
• 전체 문제의 수는 학생 수보다 크거나 같다.

예제 1에는 N = 5개의 문제 세트와 M = 4명의 학생이 있다.

• 첫 번째 학생에게는 실력 S1 = 14에 가장 가까운 난이도의 문제를 찾는다. 차이가 가장 작은 문제는 난이도 12인 문제이고, 이는 세 번째 문제 세트에서 찾을 수 있다. 따라서 P1 = 12이다.
• 두 번째 학생에게는 실력 S2 = 24에 가장 가까운 난이도의 문제를 찾는다. 다행히 네 번째 문제 세트에서 정확히 이 난이도의 문제를 찾을 수 있다. 따라서 P2 = 24이다.
• 세 번째 학생도 실력 S3 = 24에 가장 가까운 난이도의 문제를 찾는다. 난이도 24인 문제는 이미 사용했으므로 쓸 수 없다. 난이도가 가장 가까운 문제는 11이다. 12도 이미 사용했기 때문이다. 따라서 P3 = 11이다.
• 마지막으로 네 번째 학생에게는 실력 S4 = 4에 가장 가까운 문제를 찾는다. 차이가 같은 문제가 2와 6 두 개 있다. 더 쉬운 문제를 고르므로 P4 = 2이다.

예제 2에는 N = 1개의 문제 세트와 M = 1명의 학생이 있다. 유일한 문제 세트에는 문제가 하나뿐이므로 이 문제로 첫 번째이자 유일한 학생을 시험해야 한다. 따라서 P1 = 42이다.