깃발 꽂기

이 국가의 영토는 좌우로 길쭉한 모양이다. 영토는 수직선 위의 길이 $L$인 선분으로 나타낼 수 있으며, 왼쪽 끝은 좌표 $0$, 오른쪽 끝은 좌표 $L$에 놓여 있다.

영토에는 깃발이 총 $N$개 꽂혀 있다. 왼쪽에서 $i$번째 깃발은 정수 좌표 $X_i$에 꽂혀 있다. 깃발이 한 군데에 몰려 있으면 보기 좋지 않으므로, 임의의 두 깃발은 적어도 $K$ 이상 떨어져 있어야 한다. 현재 꽂혀 있는 $N$개의 깃발은 이 규정을 지킨다.

새해를 맞아 이 국가는 깃발 $M$개를 추가로 꽂기로 했고, 공무원인 당신이 이 일을 맡았다. 당신은 특정 좌표에서 깃발 $M$개를 들고 출발한다. 영토 안에서 좌우로 자유롭게 이동할 수 있고, 현재 위치가 정수 좌표라면 언제든지 깃발을 꽂을 수 있다. 다만 이미 꽂힌 깃발을 포함하여 임의의 두 깃발이 적어도 $K$ 이상 떨어지도록 깃발 $M$개를 꽂아야 한다. 규정을 지키면서 깃발 $M$개를 꽂을 수 없는 경우는 주어지지 않는다.

당신은 출발지 후보 $Q$개 중 하나에서 출발하려 한다. $i$번째 후보는 정수 좌표 $P_i$에 있다. 각 후보에서 출발할 때 깃발 $M$개를 모두 꽂는 데 필요한 최소 이동 거리를 구하라.

첫 번째 줄에 $N$, $M$, $K$, $L$, $Q$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $X_i$가 공백으로 구분되어 주어진다.

이후 $Q$개의 줄에 걸쳐, 이 중 $i$번째 줄에는 $P_i$가 주어진다.

$Q$개의 줄에 걸쳐, 이 중 $i$번째 줄에는 $i$번째 후보에서 출발할 때 깃발 $M$개를 모두 꽂는 데 필요한 최소 이동 거리를 출력한다.

• 주어지는 모든 수는 정수이다.
• $1 \le N, Q \le 200\,000$
• $1 \le M, K, L \le 10^9$
• $0 \le X_i \le L$ $(1 \le i \le N)$
• $X_i + K \le X_{i+1}$ $(1 \le i \le N-1)$
• $0 \le P_i \le L$ $(1 \le i \le Q)$
• 규정을 지키면서 깃발을 추가로 $M$개 꽂을 수 있다.