Rolete

One Saturday afternoon, Luka woke up from a nap and remembered that COCI was today. Before the contest he had only one thing to do: raise the blinds.

Luka's room has $n$ blinds. The $i$-th blind is lowered by $a_i$ centimeters from the top of the window. He can raise the blinds in two ways:

• He can start lifting any single blind manually. This takes $t$ seconds for each centimeter.
• He can press a button that starts raising all blinds in parallel at the same speed.

While all blinds are still rising, the button raises each blind by 1 centimeter in $s$ seconds. After $r$ blinds have already reached the top, the system slows down, and each remaining blind needs $s + k \cdot r$ seconds to rise by 1 centimeter.

His younger brother Marin came into the room and asked $q$ questions. Each question asks for the minimum time needed to raise the blinds so that every blind is lowered by at most $h$ centimeters. Marin asks every question with respect to the initial state of the blinds.

Luka always raises each blind by a whole number of centimeters.

The first line contains integers $n$, $t$, $s$, and $k$ ($1 \le n, t, s \le 10^5$, $0 \le k \le 10^5$), the number of blinds, the time to raise a blind manually by 1 centimeter, the time to raise a blind with the button, and the slowing factor of parallel raising.

The second line contains $n$ integers $a_i$ ($0 \le a_i \le 10^5$), the initial state of the blinds.

The third line contains an integer $q$ ($1 \le q \le 10^5$), the number of questions.

The fourth line contains $q$ integers $h_i$ ($0 \le h_i \le 10^5$), the required maximal blind height for each question.

Print $q$ numbers on a single line. The $i$-th number is the minimum time needed to raise the blinds so that they are lowered by at most $h_i$ centimeters.