빛의 돌 시뮬레이션

기록에 따르면 다섯 개의 돌 중 하나인 '빛의 돌'은 신비한 빛을 내어 어두운 밤에도 도시를 밝혔다고 합니다. 그러나 시간이 지날수록 빛의 세기는 점점 약해졌고, 결국 빛은 완전히 사라진 것으로 보입니다.

폴리매스 문명을 분석하기 위해 고대인들의 상황을 간단히 나타내 봅시다. 시간 0에 빛의 돌이 수직선의 원점에 있었고, 그 주변에는 $N$명의 사람이 살고 있었습니다. 사람 $i$의 초기 거주지는 $a_1, a_2, \cdots, a_N$입니다. 빛의 돌은 좌우로 빛을 냅니다.

빛의 돌은 처음에 좌우로 $L$만큼의 범위를 비춥니다. 이 범위는 시간이 1 지날 때마다 1씩 줄어듭니다. 즉, 시간 $t$ ($t \le L$)에 빛의 돌이 위치 $x$에 있다면, 빛이 비추는 범위는 $[x-(L-t), x+(L-t)]$입니다. 고대인들은 빛의 돌 말고는 밤을 밝힐 방법이 없었으므로, 빛이 비추는 범위 안으로 이주해야 했습니다. 한 사람이 자신의 거주지를 1 옮기는 데 드는 비용은 1입니다.

사람들이 이주하는 것보다 빛의 돌을 옮기는 편이 효율적이라면, 큰 비용을 들여서라도 빛의 돌을 움직였습니다. 빛의 돌을 거리 1만큼 옮기는 데 드는 비용은 $K$입니다. 빛의 돌과 거주지를 모두 옮기는 것도 가능합니다.

연구를 위해 $Q$가지 상황을 가정했습니다. 각 상황은 정수 $t_i$로 주어지며, 그 상황에 해당하는 시간을 나타냅니다. 모든 $t_i$에 대하여, 고대인들이 시간 $t_i$가 될 때까지 빛의 돌로부터 빛을 얻기 위해 거주지나 빛의 돌을 옮기는 데 쓴 최소 비용을 구하세요.

첫 줄에는 사람의 수 $N$, 상황의 수 $Q$, 빛의 돌이 빛을 내는 범위 $L$, 빛의 돌을 옮기는 데 드는 비용 $K$가 주어집니다.

둘째 줄에는 수직선상에서 각 사람의 초기 거주지 위치 $a_1, a_2, \cdots, a_N$이 주어집니다.

셋째 줄에는 $Q$개의 상황을 나타내는 정수 $t_1, t_2, \cdots, t_Q$가 주어집니다.

각 상황에 대한 답 $Q$개를 한 줄에 하나씩 출력합니다.

• $1 \le N \le 2 \times 10^6$
• $1 \le Q \le 2 \times 10^6$
• $1 \le L \le 10^9$
• $1 \le K \le 10^9$
• $-L \le a_i \le L$ ($1 \le i \le N$)
• $0 \le t_i \le L$ ($1 \le i \le Q$)
• $a_i \le a_{i+1}$ ($1 \le i < N$)
• $t_i \le t_{i+1}$ ($1 \le i < Q$)