컴퓨터실

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비트 정수형 변수를 사용하도록 한다.

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