OGLEDALA - Ogledala

There are M modern washbasins numbered from 1 to M from left to right in the ladies’ room of an enormous shopping centre.

Currently, there are N ladies in the restroom (numbered from 1 to N) and they’ve occupied the washbasins with numbers A1, A2, . . . , AN . Soon there will be M − N more ladies arriving (numbered from N + 1 to M in the order of arrival) that will occupy all the remaining available washbasins.

The ladies arriving primarily want their privacy, so each of them always chooses an available washbasin by the following procedure:

  • First she finds the largest consecutive series of available washbasins. If there is more than one, she chooses the left-most.
  • After that, she occupies the middle washbasin in the chosen series. If the series is of even length, she chooses the left of the two middle washbasins.

It is safe to assume that none of the ladies will leave the washbasin in the foreseeable future.

Write a programme that will, for each of Q given integers Bi , determine the label of the washbasin that will be occupied by the lady marked with Bi.

Input

The first line of input contains integers M, N and Q – the number of washbasins, the initial number of ladies in the restroom and the number of ladies for which you need to determine which washbasin they will use.

The second line of input contains N space-separated integers, the i th of those numbers is Ai – the label of the washbasin that is being used by lady i.

The third line of input contains Q space-separated integers, the i th of those numbers is Bi – the label of the lady for which we want to know which washbasin she will use.

The first N ladies in the restroom haven’t necessarily chosen their washbasins using the procedure described in the task.

The arrays A and B are strictly increasing. In other words, it holds 1 <= A1 < A2 < . . . < AN <= M and 1 <= B1 < B2 < . . . < BQ <= M.

Output

Output Q lines. The i th line must contain the label of the washbasin that will be used by the lady labeled Bi .

Constraints

1 <= N <= M <= 10^14
1 <= Q, N <= 10^5

Example

Input:
7 1 4 

2 3 4 5 Output: 2
6
1
3
Input:
10 2 4 
2 8
1 3 5 8 Output:
2
5
6
4

Clarification of the second example:
The first two ladies occupy the washbasins 2 and 8 (respectively).
The remaining ladies occupy the washbasins 5, 3, 6, 9, 1, 4, 7 and 10, respectively.

Source: Croatian Olympiad in Informatics 2015


Added by:Ivan Katanic
Date:2015-04-15
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2023-09-07 04:34:43 Oleg
Easy version: https://www.spoj.com/problems/URI/
2015-05-22 15:35:20 Ivan Katanic
Fixed.
2015-05-21 00:04:21 :D
There seems to be an issue with the input. Check if the input is empty and print nothing in that case. For example:
if (scanf("%d %d", &N, &M) != 2) return 0;
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.