Final Exam

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

Edsger prepared N problem sets. Each set consists of problems in increasing difficulty order. The i-th set can be described by two integers Ai and Bi (Ai ≤ Bi), which means the set contains problems with difficulties Ai, Ai+1, …, Bi. Among all problems from all sets, 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 receive the exact same problem, so once Edsger tests a student with some problem, he cannot use that problem again. Through countless lectures, exercises, and projects, Edsger has gauged student j to have skill level Sj and wants to give that student a problem of difficulty Sj. This is not always possible, as Edsger may not have prepared a problem of that difficulty, or he may have already given that problem to another student. Therefore, Edsger chooses for student j a problem of difficulty Pj such that |Pj−Sj| is minimal and a problem of difficulty Pj has not been given to any student before student j. If several problems tie, Edsger always chooses the easier one. The problem chosen for student j can affect the problems chosen for all students tested later, so you must process the students in the same order as they appear in the input.

Keeping track of all the problems can be fairly complicated. Can you help Edsger 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 containing two integers N and M: the number of problem sets and the number of students. N lines follow, describing the problem sets. Each of these N lines contains two integers Ai and Bi, the easiest and the hardest problem in the i-th problem set. The test case ends with a single line containing M integers S1, S2, …, SM, the 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 Pj is the difficulty of the problem given to student j.

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

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

• For the first student, we look for a problem with the difficulty closest to skill level S1 = 14. The problem with the minimum difference is the problem of difficulty 12, which is in the third problem set, so P1 = 12.
• For the second student, we look for a problem with the difficulty closest to skill level S2 = 24. Fortunately, we find a problem of exactly this difficulty in the fourth problem set, so P2 = 24.
• For the third student, we again look for a problem with the difficulty closest to skill level S3 = 24. We already used the problem of difficulty 24, so we cannot use it. The problem closest in difficulty is 11, since 12 was already used as well. Therefore P3 = 11.
• Finally, for the fourth student, we look for the problem closest to skill level S4 = 4. Two problems have the same difference: 2 and 6. We choose the easier problem, so P4 = 2.

In Sample Case #2, we have N = 1 problem set and M = 1 student. The only problem set contains just one problem, so we must use this problem to test the first and only student, so P1 = 42.