P16851 [GKS 2021 #D] 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 $2$ integers $A_i$ and $B_i$ ($A_i \le B_i$), which denotes that this set contains problems with difficulties $A_i, A_i + 1, \ldots, B_i$. Among all problems from all sets, it is guaranteed that no $2$ problems have the same difficulty. This semester Edsger has to test $M$ students. He wants to test each student with exactly $1$ problem from $1$ of his sets. No $2$ 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 $2$ 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 $2$ 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_1, S_2, \ldots, S_M$ denoting students' skill levels in the order they will be tested.

For each test case, output one line containing `Case #`$x$: $P_1$ $P_2$ $\ldots$ $P_M$, 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.

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_1 = 14$. The problem with the minimum difference is problem with difficulty $12$, which we can find in the third problem set, so $P_1 = 12$. - For the second student, we are looking for a problem with the difficulty closest to their skill level $S_2 = 24$. Fortunately, we can find a problem of this exact difficulty in the fourth problem set, so $P_2 = 24$. - For the third student, we are once again looking for a problem with the difficulty closest to the skill level $S_3 = 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_3 = 11$. - Finally, for the fourth student, we are looking for the problem closest to his skill level $S_4 = 4$. We have $2$ problems with the same difference: $2$ and $6$. We choose the easier problem, so $P_4 = 2$. In Sample Case #$2$, we have $N = 1$ problem set and $M = 1$ student. In the only problem set, there is only $1$ problem, so we have to use this problem to examine the first and only student, so $P_1 = 42$. ### Limits $1 \le T \le 100$. Among all problem sets, no $2$ problems have the same difficulty. The number of problems in total is greater than or equal to the number of students. **Test Set $1$** $1 \le N \le 1000$. $1 \le M \le 1000$. $1 \le A_i \le B_i \le 1000$ for all $i$. $1 \le S_j \le 1000$ for all $j$. **Test Set $2$** $1 \le N \le 10^5$. $1 \le M \le 10^5$. $1 \le A_i \le B_i \le 10^{18}$ for all $i$. $1 \le S_j \le 10^{18}$ for all $j$.