컴퓨터실

시간 제한4초메모리 제한512 MB

요약

빈 구간이 가장 긴 곳의 가운데 자리에 순서대로 착석할 때 주어진 순서의 학생이 앉는 자리를 구합니다.

문제

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

지금 이 실습실에는 학생 $N$ 명이 이미 앉아 있고, 각각 $A_1$ , $A_2$ , ..., $A_N$ 번 컴퓨터 앞에 앉아 있다. 곧 자습 시간이 시작되므로 학생 $M-N$ 명이 더 들어와 빈 컴퓨터를 한 대씩 쓴다.

학생은 다른 학생이 자기 모니터를 보는 것을 싫어하므로, 새로 들어오는 학생은 다음 방법으로 자리를 잡는다.

실습실에 들어온 순서는 이미 앉아 있는 학생이 앞선다. 즉 $i \le N$ 이면 $i$ 번째로 들어온 학생은 $A_i$ 번 컴퓨터에 앉아 있고, $i > N$ 이면 $i$ 번째로 들어온 학생은 위 방법으로 자리를 잡는 $(i-N)$ 번째 학생이다.

진환이는 친구 $Q$ 명과 팀 프로젝트를 해야 해서 친구들이 어디에 앉는지 알아야 한다. 다행히 진환이는 각 친구가 몇 번째로 실습실에 들어왔는지 안다. 진환이를 도와 친구 각각의 자리를 구하라.

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

둘째 줄에 정수 $N$ 개가 주어진다. $i$ 번째 값은 자리를 잡은 학생의 위치 $A_i$ 다. 이미 자리를 잡은 학생은 앞서 말한 방법으로 자리를 잡지 않았을 수도 있음에 유의하여라.

셋째 줄에 정수 $Q$ 개가 주어진다. $i$ 번째 값은 $i$ 번째 친구가 실습실에 들어온 순서 $B_i$ 다.

$A$ 와 $B$ 는 오름차순이다. 즉 항상 $1 \le A_1 < A_2 < \dots < A_N \le M$ 과 $1 \le B_1 < B_2 < \dots < B_Q \le M$ 을 만족한다.

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