시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 43 8 6 16.667%

문제

CSHS(Computer Science High School)의 실습실에는 총 M대의 컴퓨터가 일렬로 놓여있다. 이 컴퓨터는 왼쪽에 있는 것부터 순서대로 1~M의 번호가 매겨져 있다.

현재, 이 실습실에는 총 N명의 학생들이 이미 앉아있으며, 각각 A1, A2, ..., AN번 컴퓨터 앞에 앉아있다. 곧 있으면 자습시간이 시작되기 때문에 총 M-N명의 학생이 더 와서 컴퓨터를 사용할 것이다.

각 학생들은 다른 학생이 자기 컴퓨터의 모니터를 보는 것을 싫어하므로 다음과 같은 방법으로 자리를 잡을 것이다.

  • 우선 학생이 없는 연속한 컴퓨터들의 그룹 중 가장 컴퓨터가 많은 그룹을 선택한다. 만약 이런 그룹이 여러개라면 가장 왼쪽에 있는 그룹을 선택한다.
  • 그 다음, 선택한 그룹의 컴퓨터들 중 정 중앙에 있는 컴퓨터를 선택하여 자리를 잡는다. 만약 학생이 선택한 그룹의 컴퓨터가 짝수개인 경우 정중앙 2개의 컴퓨터 중 왼쪽에 있는 컴퓨터에 자리를 잡는다.

진환이는 Q명의 친구들과 함께 팀 프로젝트를 해야 하기 때문에 Q명의 친구들이 어디에 앉을 지 알아야 한다. 다행히 진환이는 각 친구가 몇 번째로 실습실에 들어갔는지 알고 있다. 진환이를 도와 각 친구들의 위치를 구하.

입력

첫 번째 줄에는 컴퓨터의 수 M, 이미 자리를 잡은 학생의 수 N, 친구의 수 Q가 주어진다.

두 번째 줄에는 N개의 정수가 주어지는데, 이 값은 자리를 잡은 학생의 위치 Ai를 나타낸다. 이미 자리를 잡은 학생들은 앞서 말한 방법으로 자리를 잡지 않았을 수도 있음에 유의하여라.

세 번째 줄에는 Q개의 정수가 주어지는데, 이 값은 각 친구가 실습실에 들어간 순서 Bi를 의미한다.

  • 1 ≤ A1 < A2 < . . . < AN ≤ M, 1 ≤ B1 < B2 < . . . < BQ ≤ M.
  • 1 ≤ Q ≤ 105, N ≤ M, 1 ≤ N ≤ 105, 1 ≤ M ≤ 1014

출력

출력은 총 Q개의 줄로 이루어진다. i번째 줄에는 i번째 친구가 자리잡은 컴퓨터의 번호를 출력한다. 처리하는 정수의 범위가 32비트 정수를 넘어가므로 64비트 정수형 변수를 사용하도록 한다.

예제 입력

7 1 4
4
2 3 4 5

예제 출력

2
6
1
3

예제 입력 2

10 2 4
2 8
1 3 5 8

예제 출력 2

2
5
6
4

힌트

예제 2 설명

처음에는 2번 컴퓨터와 8번 컴퓨터에 학생이 있다.

추가적으로 오는 8명의 학생들은 순서대로 5, 3, 6, 9, 1, 4, 7, 10번 컴퓨터에 앉을 것이다.