Jaewon đi dạo dọc theo sông Gapcheon để thư giãn tâm trạng. Dọc theo bờ sông có một đường xe đạp chạy thẳng tắp. Trên đường xe đạp có $N$ chiếc xe đạp đang di chuyển với vận tốc không đổi.

Giả sử thời điểm Jaewon bắt đầu đi dạo là $0$, và thời điểm kết thúc đi dạo là $T$. Tọa độ của chiếc xe đạp thứ $i$ là $s_i$ khi Jaewon bắt đầu đi dạo và là $e_i$ khi Jaewon kết thúc đi dạo. Đối với tất cả các xe đạp, các giá trị $s_i$ đôi một khác nhau, và các giá trị $e_i$ cũng đôi một khác nhau.

Trong suốt thời gian Jaewon đi dạo, mỗi chiếc xe đạp chỉ gặp tối đa $K$ chiếc xe đạp khác. Hai chiếc xe đạp được coi là gặp nhau khi tọa độ của chúng bằng nhau.

Jaewon muốn tính khoảng cách từ một tọa độ $x$ bất kỳ đến chiếc xe đạp gần nhất tại một thời điểm $t$ bất kỳ. Hãy giúp Jaewon giải quyết $Q$ truy vấn.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên $N, T, K$ cách nhau bởi khoảng trắng. $N$ là số lượng xe đạp, $T$ là thời điểm Jaewon kết thúc đi dạo, và $K$ là cận trên của số lần mỗi chiếc xe đạp gặp các chiếc xe đạp khác. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

Trong $N$ dòng tiếp theo, mỗi dòng chứa tọa độ đầu $s_i$ và tọa độ cuối $e_i$ của xe đạp, cách nhau bởi khoảng trắng. ($0 \le s_i, e_i \le 10^9$) Với mọi $i$, các giá trị $s_i$ đôi một khác nhau, và các giá trị $e_i$ cũng đôi một khác nhau.

Dòng tiếp theo chứa một số nguyên $Q$ biểu thị số lượng truy vấn. ($1 \le Q \le 10\,000$)

Trong $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $t, x$ cách nhau bởi khoảng trắng, biểu thị một truy vấn hỏi khoảng cách từ tọa độ $x$ đến chiếc xe đạp gần nhất tại thời điểm $t$. ($0 \le t \le T$; $0 \le x \le 10^9$)

Dữ liệu đầu vào đảm bảo rằng mỗi chiếc xe đạp gặp tối đa $K$ chiếc xe đạp khác.

Dữ liệu ra

Đối với mỗi truy vấn, in ra câu trả lời dưới dạng phân số tối giản $p / q$, mỗi truy vấn trên một dòng, trong đó $p$ là số nguyên không âm và $q$ là số nguyên dương.

Ví dụ

Dữ liệu vào 1

6 12 2
40 100
0 50
110 180
10 0
130 160
70 20
6
0 33
6 45
12 170
3 57
8 181
5 44

Dữ liệu ra 1

7/1
0/1
10/1
1/2
73/3
31/6