가로수길

보랴는 최근 꿈에서 아주 긴 가로수길을 걸었다. 길을 따라 나무가 심어져 있었고, 임의의 두 나무 사이의 거리는 모두 정수 미터이다. 길의 맨 처음과 맨 끝에는 나무가 한 그루씩 있다.

보랴는 수학을 좋아해서 길의 아름다움을 수 하나로 나타내는 식을 만들고 싶어 했다. 그는 이웃한 두 나무 사이의 최대 거리를 계산했다. 이 값을 길의 불균등도라고 부른다. 불균등도가 작을수록 보랴의 기준에서 길이 더 아름답다.

길이 너무 길어서 산책이 오래 이어졌고, 보랴는 나무를 $k$그루 더 심으면 길이 얼마나 아름다워질지 궁금해졌다. 조화를 해치지 않으려면 임의의 두 나무 사이의 거리가 모두 정수 미터여야 한다. 나무 여러 그루를 같은 지점에 심을 수 있으며, 이미 나무가 있는 지점에도 심을 수 있다. 여러 $k$에 대해 불균등도의 최솟값을 구하라.

첫 줄에 세 정수 $n$, $m$, $len$이 주어진다($2 \le n, m \le 10^6$, $1 \le len \le 10^9$). 각각 이미 심어진 나무의 수, 보랴가 관심 있는 $k$ 값의 개수, 길의 길이이다.

둘째 줄에 $n$개의 정수 $a_1, \ldots, a_n$이 주어진다($0 = a_1 < a_2 < \cdots < a_n = len$). $a_i$는 길의 시작점부터 $i$번째 나무까지의 거리(미터)이다.

셋째 줄에 $m$개의 정수 $k_1, \ldots, k_m$이 주어진다($0 \le k_i \le 10^9$). 보랴의 질문이다.

$m$개의 실수를 출력한다. 각각은 $k_1, \ldots, k_m$그루를 더 심었을 때 불균등도의 최솟값이다. 각 값은 한 줄에 하나씩 출력한다.