깃발 꽂기

BOJ 국가는 좌우로 길쭉한 영토를 가지고 있다. 영토는 수직선 상의 길이 $L$짜리 선분으로 나타낼 수 있으며, 영토의 왼쪽 끝은 좌표 $0$, 오른쪽 끝은 좌표 $L$에 각각 놓여 있다.

BOJ 국가의 영토에는 깃발이 총 $N$개 꽂혀 있는데, 이 중 왼쪽에서 $i$번째 깃발은 정수 좌표 $X_i$에 꽂혀 있다. 깃발이 너무 한 군데에 몰려 있으면 보기에 좋지 않기 때문에, 임의의 두 깃발은 적어도 $K$ 이상의 거리를 가지도록 하는 규정이 있다. 현재 꽂혀 있는 $N$개의 깃발은 이 규정을 지킨다.

신년을 맞이하여 BOJ 국가에서는 깃발 $M$개를 추가로 꽂기로 하였고, BOJ 국가의 공무원인 당신은 이것을 새해 첫 업무로 배정받았다. 깃발을 꽂기 위해서 당신은 특정 좌표에서 깃발 $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$개를 추가로 꽂을 수 있다.