Tòa tháp TOWER là một tòa tháp cực kỳ cao với một cầu thang bộ để đi lên. Cầu thang này có ~10^{100}~ bậc, được đánh số thứ tự từ dưới lên trên bắt đầu từ bậc ~0~, bậc ~1~ và cứ tiếp tục như thế. Bạn đang ở bậc ~0~ và muốn leo lên tháp. Bạn có thể đi lên bằng ~2~ loại hành động sau (không được phép đi xuống):

• Bước lên ~1~ bậc: Hành động này mất ~A~ giây.

• Nhảy lên: Nhảy từ bậc hiện tại lên bậc cao hơn đúng ~D~ bậc (bỏ qua các bậc ở giữa). Hành động này mất ~B~ giây.

Hiện tại, có một số vị trí trên cầu thang đang được thi công và các bậc đang thi công thì không thể đặt chân lên. Cụ thể, có ~N~ công trường đang hoạt động; công trường thứ ~i~ ~(1 \le i \le N)~ đang diễn ra tại các bậc từ ~L_i, L_i + 1, \dots, R_i~.

Tòa tháp TOWER có ~Q~ phòng được đánh số từ ~1~ đến ~Q~ Bạn có thể vào phòng ~j~ ~(1 \le j \le Q)~ từ bậc thứ ~X_j~ của cầu thang. Do đó, bạn muốn xác định xem mình có thể đến được mỗi phòng hay không, và nếu có thì mất ít nhất bao nhiêu giây.

Hãy xác định khả năng tiếp cận và thời gian tối thiểu để đến mỗi phòng.

Input

Tất cả các giá trị đều là số nguyên.

Dòng ~1~: Ghi hai số ~N, Q~ ~(1 \le N, Q \le 2 \cdot 10^5)~.

Dòng ~2~: Ghi ba số ~D, A, B~ ~(1 \le A, B \le 10^9,\ 2 \le D \le 10^9)~.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số ~L_i, R_i~ ~(1 \le L_i \le R_i \le 10^{15})~ là phạm vi các bậc đang thi công.

~Q~ dòng tiếp theo, dòng thứ ~j~ chứa ~X_j~ ~(1 \le X_j \le 10^{15})~ là vị trí bậc để vào phòng ~j~. Bậc ~0~ và các bậc ~X_j~ đều không nằm trong vùng đang thi công.

Output

Gồm ~Q~ dòng, dòng thứ ~j~ ghi thời gian tối thiểu để đến phòng ~j~, nếu không thể đến được phòng đó, hãy ghi ~-1~.

Scoring

Sample Input 1

3 1
4 10 35
4 5
10 12
14 14
13

Sample Output 1

120

Sample Input 2

5 10
10 1 9
7 11
25 32
37 38
43 44
50 52
6
12
18
24
30
36
42
48
54
60

Sample Output 2

6
11
17
22
-1
33
-1
44
-1
55

Notes

Với mẫu thứ nhất, ~N = 3, Q = 1, A = 10, B = 35, D = 4~, đích đến là bậc ~X = 13~. Cách đi tối ưu là:

• Đi bộ từ ~0 \rightarrow 1 \rightarrow 2 \rightarrow 3~ hết ~30~ giây

• Nhảy từ bậc ~3~ lên bậc ~7~ hết ~35~ giây

• Đi bộ từ ~7 \rightarrow 8 \rightarrow 9~ hết ~20~ giây

• Nhảy từ ~9~ lên ~13~ hết ~35~ giây.

Các kết quả ở mẫu thứ hai giải thích tương tự ví dụ trên.