Computer Lab

The lab at CSHS (Computer Science High School) has $M$ computers in a row. The computers are numbered $1$ to $M$ from left to right.

$N$ students are already sitting in the lab, at computers $A_1$, $A_2$, ..., $A_N$. Self study starts soon, so $M-N$ more students come in and use one free computer each.

A student dislikes having another student look at their monitor, so each student who comes in takes a seat this way.

• Choose the run of consecutive computers with no student that holds the most computers. If there are several such runs, choose the leftmost one.
• Sit at the computer in the exact middle of the chosen run. If the run holds an even number of computers, sit at the left one of the two middle computers.

The students who are already seated entered first. So for $i \le N$, the $i$-th student to enter sits at computer $A_i$, and for $i > N$, the $i$-th student to enter is the $(i-N)$-th student who takes a seat by the rule above.

Jinhwan has a team project with $Q$ friends, so he needs to know where they sit. He knows the position of each friend in the entering order. Help Jinhwan and find the seat of each friend.

The first line contains the number of computers $M$, the number of students already seated $N$, and the number of friends $Q$.

The second line contains $N$ integers. The $i$-th value is the position $A_i$ of a seated student. Note that the students already seated may not have taken their seats by the rule above.

The third line contains $Q$ integers. The $i$-th value is $B_i$, the position of the $i$-th friend in the order of entering the lab.

$A$ and $B$ are ascending. That is, $1 \le A_1 < A_2 < \dots < A_N \le M$ and $1 \le B_1 < B_2 < \dots < B_Q \le M$ always hold.

Print $Q$ lines. Line $i$ holds the number of the computer where the $i$-th friend sits. The integers involved go past the range of a 32-bit integer, so use a 64-bit integer type.

• $1 \le N \le 10^5$
• $N \le M \le 10^{18}$
• $1 \le Q \le \min(M, 10^5)$