Bóng tối

Trên mặt phẳng toạ độ có một nguồn sáng điểm đang di chuyển. Nguồn sáng đi thẳng từ điểm $(a,s_y)$ đến điểm $(b,s_y)$ (với $s_y<0$) theo đoạn thẳng nối hai điểm này, với vận tốc $1$ đơn vị mỗi giây.

Trên trục $Ox$ có một hàng rào gồm $n$ đoạn thẳng rời nhau. Đoạn thứ $i$ nối hai điểm $(l_i,0)$ và $(r_i,0)$.

Một điểm $(x,y)$ được xem là nằm trong bóng tối tại một thời điểm nếu đoạn thẳng nối $(x,y)$ với vị trí hiện tại của nguồn sáng cắt hoặc chạm vào một đoạn nào đó của hàng rào.

Cho $q$ điểm truy vấn. Với mỗi điểm, hãy tính tổng thời gian điểm đó nằm trong bóng tối trong suốt quá trình nguồn sáng di chuyển từ $(a,s_y)$ đến $(b,s_y)$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $s_y$, $a$, $b$.
• Dòng thứ hai chứa số nguyên $n$: số đoạn của hàng rào.
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$: các đoạn của hàng rào, cho theo thứ tự tăng dần và không giao nhau, không chạm nhau ($r_{i-1}<l_i$).
• Dòng tiếp theo chứa số nguyên $q$: số điểm cần xử lí.
• $q$ dòng cuối, mỗi dòng chứa hai số nguyên $x_i$ và $y_i$: điểm cần xử lí.

Dữ liệu ra

Gồm $q$ dòng, dòng thứ $i$ chứa một số thực: tổng thời gian điểm thứ $i$ nằm trong bóng tối. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-6}$.

Ràng buộc

• $-{10}^9\le s_y<0$, $1\le a<b\le {10}^9$.
• $1\le n\le 2·{10}^5$.
• $1\le l_i<r_i\le {10}^9$ và $r_{i-1}<l_i$.
• $1\le q\le 2·{10}^5$.
• $1\le x_i,y_i\le {10}^9$.

Ví dụ