23013번 - Final Exam 서브태스크다국어

It's time for the final exam in algorithms and data structures!

Edsger prepared N sets of problems. Each set consists of problems in an increasing difficulty sequence; the i-th set can be described by two integers A_i and B_i (A_i ≤ B_i), which denotes that this set contains problems with difficulties A_i, A_i+1, …, B_i. Among all problems from all sets, it is guaranteed that no two problems have the same difficulty.

This semester Edsger has to test M students. He wants to test each student with exactly one problem from one of his sets. No two students can get the exact same problem, so when Edsger tests a student with some problem, he cannot use this problem anymore. Through countless lectures, exercises, and projects, Edsger has gauged student number j to have skill level S_j, and wants to give that student a problem with difficulty S_j. Unfortunately, this is not always possible, as Edsger may have not prepared a problem of this difficulty, or he may have already asked this problem to some other student earlier. Therefore, Edsger will choose for the j-th student a problem of difficulty P_j, in a way that |P_j−S_j| is minimal and a question of difficulty P_j was not already given to any of the students before the j-th student. In case of ties, Edsger will always choose the easier problem. Note that the problem chosen for the j-th student may affect problems chosen for all the students tested later, so you have to process students in the same order as they appear in the input.

As keeping track of all the problems can be fairly complicated, can you help Edsger and determine which problems he should give to all of his students?

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case begins with a line which contains two integers N and M: the number of problem sets, and the number of students, respectively. N lines follow, describing the problem sets. Each of these N lines consists of two integers A_i and B_i denoting the easiest and the hardest problem in the i-th problem set. Finally, the test case ends with a single line with M integers S₁, S₂, …, S_M denoting students' skill levels in the order they will be tested.

For each test case, output one line containing Case #x: P1P2…PM, where x is the test case number (starting from 1) and P_j is a difficulty of a problem that will be given to the j-th student.

• 1 ≤ T ≤ 100.
• Among all problem sets, no two problems have the same difficulty.
• The number of problems in total is greater than or equal to the number of students.

시간 제한: 20 초

• 1 ≤ N ≤ 1000.
• 1 ≤ M ≤ 1000.
• 1 ≤ A_i ≤ B_i ≤ 1000 for all i.
• 1 ≤ S_j ≤ 1000 for all j.

시간 제한: 40 초

• 1 ≤ N ≤ 10⁵.
• 1 ≤ M ≤ 10⁵.
• 1 ≤ A_i ≤ B_i ≤ 10¹⁸ for all i.
• 1 ≤ S_j ≤ 10¹⁸ for all j.

In Sample Case #1, we have N = 5 problem sets and M = 4 students.

• For the first student, we are looking for a problem with the difficulty closest to their skill level S₁ = 14. The problem with the minimum difference is problem with difficulty 12, which we can find in the third problem set, so P₁ = 12.
• For the second student, we are looking for a problem with the difficulty closest to their skill level S₂ = 24. Fortunately, we can find a problem of this exact difficulty in the fourth problem set, so P₂ = 24.
• For the third student, we are once again looking for a problem with the difficulty closest to the skill level S₃ = 24. As we already used the problem with difficulty 24, we cannot use this problem. The problem closest in difficulty is 11, as 12 was already used as well. Therefore P₃ = 11.
• Finally, for the fourth student, we are looking for the problem closest to his skill level S₄ = 4. We have two problems with the same difference: 2 and 6. We choose the easier problem, so P₄ = 2.

In Sample Case #2, we have N = 1 problem set and M=1 student. In the only problem set, there is only one problem, so we have to use this problem to examine the first and only student, so P₁ = 42.