21561번 - 빛의 돌 시뮬레이션 서브태스크

기록에 따르면, 다섯 개의 돌 중 하나인 ‘빛의 돌’은 신비한 빛을 내어 어두운 밤까지 도시를 밝혔다고 합니다. 하지만 시간이 지날수록 빛의 세기는 점점 줄어들고, 끝내 빛이 소멸된 것으로 보입니다.

폴리매스 문명을 분석하기 위해, 고대인들의 상황을 간략하게 나타내어 봅시다. 초기(시간 0)에 수직선 위의 원점에 빛의 돌이 있었고, 그 주변에 $N$명의 사람들이 살고 있었습니다. 각 사람들의 초기 거주지는 $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$에 대하여, 고대인들이 시간 $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$)