Jaewon poszedł na spacer nad rzekę Gapcheon, aby się przewietrzyć. Wzdłuż brzegu rzeki biegnie w linii prostej ścieżka rowerowa. Po ścieżce rowerowej porusza się $N$ rowerów, każdy ze stałą prędkością.

Niech moment, w którym Jaewon rozpoczął spacer, wynosi $0$, a moment, w którym zakończył spacer, wynosi $T$. Współrzędna $i$-tego roweru wynosi $s_i$, gdy Jaewon rozpoczął spacer, oraz $e_i$, gdy Jaewon zakończył spacer. Dla wszystkich rowerów wartości $s_i$ są parami różne, a wartości $e_i$ również są parami różne.

Podczas spaceru Jaewona każdy rower spotyka co najwyżej $K$ innych rowerów. Uznajemy, że dwa rowery spotykają się, gdy ich współrzędne stają się równe.

Jaewon zapragnął obliczyć, jaka jest odległość w dowolnym momencie $t$ od dowolnej współrzędnej $x$ do najbliższego roweru. Pomóż Jaewonowi rozwiązać $Q$ zapytań.

Wejście

W pierwszym wierszu podane są liczby całkowite $N, T, K$ oddzielone spacjami. $N$ to liczba rowerów, $T$ to moment zakończenia spaceru przez Jaewona, a $K$ to górne ograniczenie na liczbę spotkań każdego roweru z innymi rowerami. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

W kolejnych $N$ wierszach podane są początkowa współrzędna $s_i$ oraz końcowa współrzędna $e_i$ roweru, oddzielone spacją. ($0 \le s_i, e_i \le 10^9$) Dla każdego $i$ wartości $s_i$ są parami różne, a wartości $e_i$ również są parami różne.

W kolejnym wierszu podana jest liczba całkowita $Q$ oznaczająca liczbę zapytań. ($1 \le Q \le 10\,000$)

W kolejnych $Q$ wierszach podane są liczby całkowite $t, x$ oddzielone spacją. Oznaczają one zapytanie o odległość od współrzędnej $x$ do najbliższego roweru w momencie $t$. ($0 \le t \le T$; $0 \le x \le 10^9$)

Gwarantowane jest, że w podanych danych wejściowych każdy rower spotyka co najwyżej $K$ rowerów.

Wyjście

Dla każdego zapytania wypisz odpowiedź w postaci ułamka nieskracalnego $p / q$, po jednej w każdym wierszu, gdzie $p$ jest nieujemną liczbą całkowitą, a $q$ jest dodatnią liczbą całkowitą.

Przykład

Wejście 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

Wyjście 1

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