서커스

새 서커스 공연은 공연장 천장에 매달린 아주 긴 밧줄을 쓴다. 공연장 입구와 모든 밧줄은 하나의 직선 위에 놓여 있다. 천장은 평평하고 높이는 $10^{18}$이며, 밧줄은 아무 데도 걸리지 않은 채 바닥까지 늘어져 있다. 곡예사는 밧줄에서 밧줄로 옮겨 다니며 입구에서 $M$ 이상 떨어진 지점까지 가야 한다.

밧줄은 모두 $N$개다. $i$번 밧줄은 천장을 따라 잰 입구로부터의 거리가 $P_i$인 위치에 매달려 있다.

곡예사는 신중해서 아무렇게나 뛰지 않는다. 곡예사가 $i$번 밧줄을 천장에서 $S$만큼 떨어진 지점에서 잡고 있다고 하자. 곡예사는 잡고 있는 밧줄에 매달려 그네처럼 흔들릴 수 있다. 흔들리다가 입구에서 $M$ 이상 떨어진 지점에 닿으면 임무를 마친 것으로 본다. 흔들리는 동안 곡예사는 지금 잡은 밧줄에서 $S$ 이하만큼 떨어진 위치에 매달린 다른 밧줄을 잡을 수 있다. 즉 $|P_i - P_j| \le S$이면 $j$번 밧줄을 잡을 수 있다. 이제 곡예사는 $i$번 밧줄과 $j$번 밧줄을 함께 쥐고 있다. 이 상태에서 곡예사는 $j$번 밧줄을 쥔 채 $i$번 밧줄을 타고 올라간다. $i$번 밧줄이 천장에 닿는 지점까지 올라가면 $j$번 밧줄이 천장을 따라 팽팽하게 당겨진다. 이때부터 곡예사는 $j$번 밧줄을 천장에서 $|P_i - P_j|$만큼 떨어진 지점에서 잡은 채로 움직임을 이어 간다.

공연 감독은 입구에서 천장을 따라 $D$만큼 떨어진 위치에 임시 밧줄을 하나 더 매달려고 한다. 공연은 이 밧줄에서 시작한다. 곡예사의 임무는 이 밧줄에서 출발해 공연장 반대편 끝, 즉 입구에서 $M$ 이상 떨어진 지점까지 가는 것이다. 밧줄을 옮겨 잡는 동안 임시 밧줄은 다른 밧줄과 똑같이 취급한다. 곡예사가 임무를 마칠 수 있으려면 임시 밧줄을 천장에서 최소 얼마나 떨어진 지점에서 잡아야 하는지 구하는 프로그램을 작성하시오.

예를 들어 밧줄이 3개이고 각각 입구에서 0, 3, 6만큼 떨어진 위치에 매달려 있으며 목표가 $M = 8$인 경우를 보자. 임시 밧줄은 입구에서 4만큼 떨어진 위치에 있다. 곡예사가 임시 밧줄(굵은 선)을 천장에서 3만큼 떨어진 지점에서 잡으면, 흔들려서 입구에서 6만큼 떨어진 밧줄을 잡을 수 있다. 그 밧줄을 잡은 뒤 임시 밧줄을 타고 천장까지 올라가면 입구에서 6만큼 떨어진 밧줄을 천장에서 $6 - 4 = 2$만큼 떨어진 지점에서 잡게 된다. 여기서 다시 흔들리면 입구에서 8만큼 떨어진 목표 지점에 닿는다.

감독은 임시 밧줄을 매달 위치를 여러 개 생각해 두었고, 위치마다 답을 알고 싶어 한다.

첫째 줄에 밧줄의 개수 $N$과 목표 거리 $M$이 공백으로 구분되어 주어진다.

다음 $N$개 줄에 밧줄의 위치 $P_i$가 한 줄에 하나씩 주어진다.

그다음 줄에 질의의 개수 $Q$가 주어진다.

마지막 $Q$개 줄에 임시 밧줄의 위치 $D$가 한 줄에 하나씩 주어진다.

$Q$개 줄에 걸쳐 각 질의의 답을 입력에 주어진 순서대로 출력한다. 각 줄에는 곡예사가 임무를 마칠 수 있도록 임시 밧줄을 잡아야 하는, 천장으로부터의 최소 거리를 출력한다.

• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $1 \le M \le 10^9$
• $0 \le P_i < M$
• $0 \le D < M$
• 입력으로 주어지는 수는 모두 정수이다.
• 서로 다른 밧줄이 같은 위치에 매달려 있을 수 있다.

밧줄이 0, 3, 6에 있고 $M = 8$인 경우를 보자.

임시 밧줄이 4에 있으면 답은 2이다. 임시 밧줄을 천장에서 2만큼 떨어진 지점에서 잡으면 $|4 - 6| = 2$이므로 6에 있는 밧줄을 잡을 수 있고, 임시 밧줄을 타고 올라가면 6에 있는 밧줄을 천장에서 2만큼 떨어진 지점에서 잡게 되어 $6 + 2 = 8$에 닿는다. 4에서 0, 3, 6을 차례로 거쳐 8에 닿는 방법도 있지만, 그러려면 임시 밧줄을 처음에 천장에서 4만큼 떨어진 지점에서 잡아야 한다.

임시 밧줄이 5에 있으면 답은 3이다. 이때는 다른 밧줄을 거치지 않고 임시 밧줄에서 곧바로 목표 지점에 닿는다.