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

Luka có ~n~ cái rèm trong phòng, cái thứ i được hạ xuống cách đầu cửa sổ ~a_i~ cm. Anh ta có thể nâng rèm theo hai cách:

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

Tốc độ nâng rèm bằng một nút được xác định như sau: Nếu tất cả các rèm vẫn tăng lên thì mỗi rèm sẽ tăng thêm ~1~ cm trong ~s~ giây. Nếu ~r~ rèm đã được nâng lên trên cùng thì hệ thống sẽ chậm lại. Sau đó sẽ mất ~s + k \times r~ giây để tất cả các tấm rèm còn lại tăng thêm ~1~ cm.

COCI sắp bắt đầu và Luka muốn nâng rèm của mình càng sớm càng tốt. Trong khi đó, anh trai Marin của anh vào phòng và hỏi anh những câu hỏi: Thời gian tối thiểu bạn cần để nâng rèm sao cho tất cả chúng đều hạ xuống tối đa ~h~ cm? Marin quan tâm đến câu trả lời cho từng câu hỏi khi xem xét trạng thái ban đầu của rèm.

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

Lưu ý: Luka sẽ luôn nâng rèm lên một giá trị nguyên cm.

Input

• Dòng đầu tiên gồm các số nguyên ~n, t, s, k~ (~1 \leq n, t, s \leq 10^5, 0 \leq k \leq 10^5~) là số rèm, thời gian để kéo một rèm bằng tay, thời gian để nâng tất cả các rèm lên ~1~ cm bằng việc ấn nút và hệ số của việc nâng tất cả các rèm bằng ấn nút.
• Dòng thứ hai gồm ~n~ số nguyên ~a_i~ (~0 \leq a_i \leq 10^5~) là trạng thái ban đầu của những chiếc rèm.
• Dòng thứ ba gồm số nguyên ~q~ (~1 \leq q \leq 10^5~) là số câu hỏi.
• Dòng thứ tư gồm ~q~ số nguyên ~h_i~ (~0 \leq h_i \leq 10^5~) là độ hạ xuống tối đa trong câu hỏi thứ ~i~.

Output

Trong một dòng, in ra ~q~ số nguyên, với số thứ ~i~ là câu trả lời cho câu hỏi thứ ~i~.

Scoring

1. ~n, q, a_i, h_i \leq 100~ (16 điểm)

2. ~k = 0~ (26 điểm)

3. ~q = 1~ (32 điểm)

4. Không có ràng buộc gì thêm (36 điểm)

Sample Input 1

3 2 5 1
2 2 4
3
2 0 1

Sample Output 1

4 14 9

Sample Input 2

2 3 4 0
3 1
3
3 2 0

Sample Output 2

0 3 10

Sample Input 3

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

Sample Output 3

9 18 47

Explanation

Ở ví dụ đầu tiên:

• Luka kéo bằng tay rèm thứ ba lên ~2~ cm, mất ~2 \times 2 = 4~ giây.
• Luka kéo bằng tay rèm thứ ba lên ~2~ cm, rồi bấm nút để tất cả cùng được kéo lên ~2~ cm, mất ~2\times 2 + 2 \times 5 = 14~ giây.
• Luka kéo bằng tay rèm thứ ba lên ~2~ cm, rồi bấm nút để tất cả cùng được kéo lên ~1~ cm, mất ~2\times 2 + 1 \times 5 = 9~ giây.