Một ngày thứ Bảy, Hạo thức dậy sau giấc ngủ trưa và nhớ ra: hôm nay là ACOJ! Chỉ có một việc anh cần làm trước khi thi: kéo rèm cửa lên.

Hạo có \(n\) rèm cửa trong phòng, trong đó rèm thứ \(i\) được hạ xuống \(a_i\) centimet từ đỉnh cửa sổ. Anh có thể kéo rèm theo hai cách:

• Anh có thể bắt đầu kéo bất kỳ rèm đơn lẻ nào bằng tay. Với phương pháp này, anh mất \(t\) giây để kéo rèm lên \(1\) centimet.
• Anh có thể nhấn một nút, bắt đầu kéo tất cả các rèm song song với cùng tốc độ.

Tốc độ kéo rèm bằng nút được định nghĩa như sau: Nếu tất cả các rèm vẫn đang được kéo lên, mỗi rèm sẽ được kéo lên \(1\) centimet trong \(s\) giây. Nếu \(r\) rèm đã được kéo lên hết thì hệ thống sẽ chậm lại. Khi đó sẽ mất \(s + k \times r\) giây để tất cả các rèm còn lại được kéo lên \(1\) centimet.

ACOJ sắp bắt đầu, và Hạo muốn kéo rèm càng nhanh càng tốt. Trong khi đó, anh trai Thái bước vào phòng và hỏi anh \(q\) câu hỏi: Thời gian tối thiểu cần để kéo các rèm sao cho tất cả đều được hạ xuống tối đa \(h\) centimet là bao nhiêu? Thái quan tâm đến câu trả lời cho mỗi câu hỏi xét từ trạng thái ban đầu của các rèm.

Họ nhận ra rằng không có đủ thời gian để suy nghĩ về nó trước ACOJ. May mắn thay, bài toán vừa xuất hiện ở đây! Giúp họ giải quyết nó!

Lưu ý: Hạo luôn kéo rèm lên một số nguyên centimet.

Đầu vào

• Dòng đầu tiên chứa các số nguyên \(n, t, s\) và \(k\) \((1 \le n, t, s \le 10^5, 0 \le k \le 10^5)\), số lượng rèm, thời gian cần để kéo rèm bằng tay, thời gian cần để kéo rèm bằng nút và hệ số chậm của việc kéo song song.
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((0 \le a_i \le 10^5)\), trạng thái ban đầu của các rèm.
• Dòng thứ ba chứa số nguyên \(q\) \((1 \le q \le 10^5)\), số câu hỏi.
• Dòng thứ tư chứa \(q\) số nguyên \(h_i\) \((0 \le hi \le 10^5)\), độ cao rèm tối đa cần thiết.

Đầu ra

• Trên dòng đầu tiên và duy nhất, in \(q\) số, số thứ \(i\) là thời gian tối thiểu để kéo các rèm sao cho chúng được hạ xuống tối đa \(h_i\) centimet.

Chấm điểm

Input 1

3 2 5 1
2 2 4
3
2 0 1

Output 1

4 14 9

Input 2

2 3 4 0
3 1
3
3 2 0

Output 2

0 3 10

Input 3

4 3 10 3
2 4 5 6
3
4 3 0

Output 3

9 18 47

Làm rõ ví dụ đầu tiên:

Để có tất cả các rèm được hạ xuống tối đa 2 centimet, Hạo cần kéo rèm thứ ba lên 2 centimet bằng tay. Cách nhanh nhất để làm điều này là kéo nó bằng tay. Điều này sẽ mất 4 giây.

Nếu tất cả các rèm cần được kéo lên hoàn toàn, Hạo có thể kéo rèm thứ ba lên 2 centimet bằng tay trước. Bây giờ anh có thể nhấn nút và để các rèm kéo lên song song 2 centimet. Tổng cộng, điều đó sẽ mất 4 + 10 = 14 giây.

Tương tự, nếu các rèm cần được hạ xuống tối đa 1 centimet, Hạo sẽ kéo rèm thứ ba lên 2 centimet trước, sau đó kéo tất cả các rèm cùng nhau lên 1 centimet. Tổng thời gian kéo sẽ là 9 giây.