Trong khu rừng già, chú khỉ KONG đang thực hiện một hành trình trên một đường thẳng từ thời điểm \(0\) đến thời điểm \(T\). KONG có hai chế độ di chuyển:

• Chế độ \(1\) (Leo trèo): tốc độ \(a\) mét/giây.
• Chế độ \(2\) (Đu dây): tốc độ \(b\) mét/giây.

KONG bắt đầu hành trình (thời điểm \(t = 0\)) với Chế độ 1. Trong hành trình, KONG nhận được \(n\) mệnh lệnh thay đổi chế độ. Mệnh lệnh thứ \(i\) cho biết: tại thời điểm \(t_i\), KONG chuyển sang chế độ \(m_i\) và duy trì chế độ đó cho đến khi nhận được mệnh lệnh tiếp theo hoặc đến hết thời điểm \(T\).

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn gồm \(2\) số nguyên \(L, R\) yêu cầu tính tổng quãng đường (đơn vị mét) mà KONG đã di chuyển từ giây thứ \(L\) đến giây thứ \(R\) (gồm cả giây \(L\) và giây \(R\)).

Input

• Dòng đầu tiên chứa \(5\) số nguyên dương \(n, T, Q, a, b\) (\(1 \le n, Q \le 10^5\); \(1 \le T \le 10^9\); \(1 \le a, b \le 10^6\)).
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa \(2\) số nguyên \(t_i\) và \(m_i\) (\(0 \le t_i \le T\); \(m_i \in \{1, 2\}\)). Các \(t_i\) được cho theo thứ tự tăng dần.
• \(Q\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên \(L, R\) (\(0 \le L < R \le T\)).

Output

• Gồm \(Q\) dòng, mỗi dòng chứa một số nguyên duy nhất là quãng đường tương ứng với truy vấn.

Example

3 10 2 3 7
1 2
4 1
7 2
0 6
3 10

30
37

Scoring

• \(25\%\) số test: \(a = b\).
• \(25\%\) số test: \(n, Q \le 1000\).
• \(50\%\) số test: không có ràng buộc gì thêm.