Problem G

Starting School

 

The first day of school is a very memorable day to everyone. Po is starting school from today and Po is very excited. As this is Po’s first day at school, no one is assigned roll number yet. So all the students form a line in the school field and they are being assigned roll number one by one. The teacher is a bit crazy. Instead of assigning roll number from 1, she starts assigning them one by one in a random fashion. Po watches this madness for the first K students and then steps up. Po says Po can assign them very easily for the rest of the students. The idea is very simple. Roll number should be unique and a student should get the smallest roll number that has not been assigned yet to any of the students. For example if K = 4, total number of students are 10 and the first K students’ roll numbers are 1, 3, 5, 10 then the next 6 roll numbers should be 2, 4, 6, 7, 8 and 9.

 

Though this is a very good idea, the teacher got mad at Po. So she starts asking the roll number for various students. As there are many students, Po is feeling helpless. Can you help Po?

 

Input

 

First line will contain an integer T (T <= 30), the number of test cases. Each case will start with three integers N (0 < N <= 109), K (0 < K <= 50,000 and K <= N) and Q (0 < Q <= 50,000). N is the total number of students, K is described earlier and Q is the number of queries of the crazy teacher. Next line will contain K distinct integers, the first K roll number assigned by the teacher. These values will be between 1 and 1000000000 (inclusive). Next will be Q integers, each indicating a position of students. These values will be between 1 and N (inclusive). (Large input output file, use faster I/O)

 

Output

 

For each case print one line “Case T:” where T is the case number. Then for each query print one line with the roll number of the student standing on the queried position. See sample I/O for clarity.

 

Sample Input

Output for Sample Input

2

10 4 4

1 3 5 2

5 6 9 10

10 3 2

10 1 9

4 10

Case 1:

4

6

9

10

Case 2:

2

8

 

 

Problemsetter: Hasnain Heickal

Special Thanks: Md. Mahbubul Hasan