Rolete

토요일 오후, 낮잠에서 깬 루카는 오늘이 COCI 대회 날이라는 것을 떠올렸다. 대회 전에 해야 할 일은 블라인드를 올리는 것 하나뿐이었다.

루카의 방에는 블라인드가 $n$개 있다. $i$번째 블라인드는 창문 위쪽에서 $a_i$cm 내려와 있다. 루카는 다음 두 가지 방법으로 블라인드를 올릴 수 있다.

• 블라인드 하나를 골라 직접 올릴 수 있다. 이 방법은 1cm를 올리는 데 $t$초가 걸린다.
• 버튼을 누를 수 있다. 버튼을 누르면 모든 블라인드가 같은 속도로 동시에 올라간다.

아직 올라가는 블라인드가 모두 남아 있으면, 버튼으로 블라인드 하나를 1cm 올리는 데 $s$초가 걸린다. 이미 $r$개의 블라인드가 꼭대기에 도달했다면 시스템이 느려져서, 남은 블라인드 하나를 1cm 올리는 데 $s + k \cdot r$초가 걸린다.

동생 마린이 방에 들어와 질문 $q$개를 했다. 각 질문은 모든 블라인드가 최대 $h$cm 아래에 있도록 하려면 최소 몇 초가 걸리는지 묻는다. 마린은 블라인드의 초기 상태를 기준으로 질문한다.

루카는 블라인드를 항상 정수 cm 단위로 올린다.

첫 줄에 정수 $n$, $t$, $s$, $k$가 주어진다 ($1 \le n, t, s \le 10^5$, $0 \le k \le 10^5$). 각각 블라인드의 개수, 직접 1cm 올리는 데 걸리는 시간, 버튼으로 1cm 올리는 데 걸리는 시간, 동시에 올릴 때의 감속 계수이다.

둘째 줄에 블라인드의 초기 상태 $a_i$ ($0 \le a_i \le 10^5$)가 $n$개 주어진다.

셋째 줄에 질문의 개수 $q$ ($1 \le q \le 10^5$)가 주어진다.

넷째 줄에 각 질문의 최대 허용 높이 $h_i$ ($0 \le h_i \le 10^5$)가 $q$개 주어진다.

한 줄에 $q$개의 수를 출력한다. $i$번째 수는 모든 블라인드가 최대 $h_i$cm 아래에 있도록 하는 최소 시간이다.