Tháp IOI rất cao và có một cầu thang gồm \(10^{100}\) bậc, được đánh số từ dưới lên là \(0,1,\ldots\). JOI-kun đang ở bậc \(0\) và muốn đi lên. Cậu có thể thực hiện hai loại hành động sau, nhưng không được đi xuống:

• Đi lên \(1\) bậc, mất \(A\) giây.
• Nhảy từ bậc hiện tại đến bậc cao hơn đúng \(D\) bậc, bỏ qua các bậc ở giữa, mất \(B\) giây.

Hiện có \(N\) công trình trên cầu thang. Công trình thứ \(i\) nằm trên các bậc \(L_i,L_i+1,\ldots,R_i\). JOI-kun không được đặt chân lên các bậc đang thi công.

Tháp có \(Q\) phòng được đánh số từ \(1\) đến \(Q\). Có thể vào phòng \(j\) từ bậc \(X_j\). Với mỗi phòng, JOI-kun muốn biết có thể tới được bậc đó hay không và, nếu có, thời gian ít nhất cần dùng.

Cho thông tin về JOI-kun, các công trình và các phòng, hãy trả lời yêu cầu trên với mọi \(1 \le j \le Q\).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N,Q\).
• Dòng thứ hai chứa ba số nguyên \(D,A,B\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(L_i,R_i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(X_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa thời gian ít nhất, tính bằng giây, để tới bậc \(X_j\) nếu có thể; nếu không thể, in -1.

Ràng buộc

• \(1 \le N \le 200000\).
• \(1 \le Q \le 200000\).
• \(1 \le D \le 10^{12}\).
• \(1 \le A \le 1000000\) và \(1 \le B \le 1000000\).
• \(1 \le L_i \le R_i \le 10^{12}\) với mọi \(1 \le i \le N\).
• \(R_i+1<L_{i+1}\) với mọi \(1 \le i \le N-1\).
• \(1 \le X_j \le 10^{12}\) với mọi \(1 \le j \le Q\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(R_i \le 1000000\) với mọi \(i\), \(X_j \le 1000000\) với mọi \(j\).
2. \(38\) điểm: \(N \le 2000\), \(Q \le 2000\).
3. \(25\) điểm: \(A=1\), \(B=D\).
4. \(32\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

120

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

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

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2023/2024, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.