기말고사

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

Edsger는 $\mathbf{N}$개의 문제 세트를 준비했다. 각 세트는 난이도가 증가하는 순서로 나열된 문제들로 구성된다. $i$번째 세트는 두 정수 $\mathbf{A_i}$와 $\mathbf{B_i}$($\mathbf{A_i} \le \mathbf{B_i}$)로 나타낼 수 있으며, 이는 이 세트에 난이도가 $\mathbf{A_i}, \mathbf{A_i}+1, \dots, \mathbf{B_i}$인 문제들이 포함되어 있음을 뜻한다. 모든 세트의 모든 문제 중에서 난이도가 같은 두 문제는 없다는 것이 보장된다.

이번 학기에 Edsger는 $\mathbf{M}$명의 학생을 평가해야 한다. 그는 각 학생을 자신의 세트 중 하나에 있는 정확히 하나의 문제로 평가하려 한다. 서로 다른 두 학생이 정확히 같은 문제를 받을 수는 없으므로, Edsger가 어떤 문제로 한 학생을 평가하고 나면 그 문제를 더 이상 사용할 수 없다. 수많은 강의, 연습, 프로젝트를 통해 Edsger는 $j$번 학생의 실력 수준이 $\mathbf{S_j}$이라고 판단했으며, 그 학생에게 난이도 $\mathbf{S_j}$의 문제를 주고 싶어 한다. 안타깝게도 Edsger가 이 난이도의 문제를 준비하지 않았거나 이미 앞서 다른 학생에게 이 문제를 냈을 수 있으므로, 이것이 항상 가능한 것은 아니다. 따라서 Edsger는 $j$번째 학생에게 $|P_j - \mathbf{S_j}|$가 최소가 되며, 난이도 $P_j$의 문제가 $j$번째 학생보다 앞선 어떤 학생에게도 이미 주어지지 않은 방식으로 난이도 $P_j$의 문제를 선택한다. 동률인 경우 Edsger는 항상 더 쉬운 문제를 선택한다. $j$번째 학생에게 선택한 문제는 이후에 평가받는 모든 학생에게 선택되는 문제에 영향을 줄 수 있으므로, 학생들을 입력에 나타난 순서와 같은 순서로 처리해야 한다는 점에 유의한다.

모든 문제를 추적하는 것은 상당히 복잡할 수 있으므로, Edsger가 모든 학생에게 어떤 문제를 주어야 하는지 결정하도록 도와주자.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 문제 세트에 걸쳐 난이도가 같은 두 문제는 없다. 전체 문제 수는 학생 수 이상이다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 1000$. $1 \le \mathbf{M} \le 1000$. 모든 $i$에 대해 $1 \le \mathbf{A_i} \le \mathbf{B_i} \le 1000$. 모든 $j$에 대해 $1 \le \mathbf{S_j} \le 1000$.

테스트 세트 2

시간 제한: 40초. $1 \le \mathbf{N} \le 10^5$. $1 \le \mathbf{M} \le 10^5$. 모든 $i$에 대해 $1 \le \mathbf{A_i} \le \mathbf{B_i} \le 10^{18}$. 모든 $j$에 대해 $1 \le \mathbf{S_j} \le 10^{18}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 문제 세트의 수와 학생 수를 각각 나타내는 두 정수 $\mathbf{N}$과 $\mathbf{M}$이 포함된 줄로 시작한다. 이어지는 $\mathbf{N}$개의 줄은 문제 세트를 설명한다. 이 $\mathbf{N}$개 줄은 각각 두 정수 $\mathbf{A_i}$와 $\mathbf{B_i}$로 이루어지며, $i$번째 문제 세트에서 가장 쉬운 문제와 가장 어려운 문제를 나타낸다. 마지막으로 테스트 케이스는 학생들이 평가받을 순서대로 학생들의 실력 수준을 나타내는 $\mathbf{M}$개의 정수 $\mathbf{S_1}, \mathbf{S_2}, \dots,\mathbf{S_M}$가 포함된 한 줄로 끝난다.

각 테스트 케이스마다 Case #$x$: $P_1\,P_2\,\dots\,P_M$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작한다), $P_j$는 $j$번째 학생에게 주어질 문제의 난이도이다.

예제 케이스 #1에는 $\mathbf{N} = 5$개의 문제 세트와 $\mathbf{M} = 4$명의 학생이 있다.

• 첫 번째 학생에게는 그 학생의 실력 수준 $\mathbf{S_1}= 14$에 가장 가까운 난이도의 문제를 찾는다. 차이가 최소인 문제는 난이도 $12$의 문제이며, 세 번째 문제 세트에서 찾을 수 있으므로 $P_1 = 12$이다.

• 두 번째 학생에게는 그 학생의 실력 수준 $\mathbf{S_2} = 24$에 가장 가까운 난이도의 문제를 찾는다. 다행히 네 번째 문제 세트에서 정확히 이 난이도의 문제를 찾을 수 있으므로 $P_2 = 24$이다.

• 세 번째 학생에게는 다시 한번 실력 수준 $\mathbf{S_3} = 24$에 가장 가까운 난이도의 문제를 찾는다. 난이도 $24$의 문제는 이미 사용했으므로 이 문제를 사용할 수 없다. $12$도 이미 사용했으므로, 난이도가 가장 가까운 문제는 $11$이다. 따라서 $P_3 = 11$이다.

• 마지막으로 네 번째 학생에게는 그의 실력 수준 $\mathbf{S_4} = 4$에 가장 가까운 문제를 찾는다. 차이가 같은 두 문제 $2$와 $6$이 있다. 더 쉬운 문제를 선택하므로 $P_4 = 2$이다.

예제 케이스 #2에는 $\mathbf{N} = 1$개의 문제 세트와 $\mathbf{M} = 1$명의 학생이 있다. 유일한 문제 세트에는 문제가 하나뿐이므로, 첫 번째이자 유일한 학생을 평가하는 데 이 문제를 사용해야 하며, 따라서 $P_1 = 42$이다.