Jaewon machte einen Spaziergang am Fluss Gapcheon, um auf andere Gedanken zu kommen. Entlang des Flussufers verläuft ein schnurgerader Radweg. Auf dem Radweg bewegen sich $N$ Fahrräder jeweils mit konstanter Geschwindigkeit.

Sei der Zeitpunkt, zu dem Jaewon seinen Spaziergang beginnt, $0$, und der Zeitpunkt, zu dem er seinen Spaziergang beendet, $T$. Die Koordinate des $i$-ten Fahrrads ist $s_i$, als Jaewon seinen Spaziergang beginnt, und $e_i$, als Jaewon seinen Spaziergang beendet. Für alle Fahrräder sind die Werte $s_i$ paarweise verschieden, und auch die Werte $e_i$ sind paarweise verschieden.

Während Jaewon spazieren geht, begegnet jedes Fahrrad höchstens $K$ anderen Fahrrädern. Zwei Fahrräder gelten als einander begegnet, wenn ihre Koordinaten gleich werden.

Jaewon möchte nun berechnen, wie groß zu einem beliebigen Zeitpunkt $t$ der Abstand von einer beliebigen Koordinate $x$ zum nächstgelegenen Fahrrad ist. Hilf Jaewon dabei, $Q$ Anfragen zu beantworten.

Eingabe

In der ersten Zeile werden die ganzen Zahlen $N, T, K$ durch Leerzeichen getrennt gegeben. $N$ ist die Anzahl der Fahrräder, $T$ ist der Zeitpunkt, zu dem Jaewon seinen Spaziergang beendet, und $K$ ist die obere Schranke dafür, wie oft jedes Fahrrad anderen Fahrrädern begegnet. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

In den nächsten $N$ Zeilen werden jeweils die Anfangskoordinate $s_i$ und die Endkoordinate $e_i$ eines Fahrrads durch ein Leerzeichen getrennt gegeben. ($0 \le s_i, e_i \le 10^9$) Für alle $i$ sind die Werte $s_i$ paarweise verschieden, und auch die Werte $e_i$ sind paarweise verschieden.

In der nächsten Zeile wird eine ganze Zahl $Q$ gegeben, die die Anzahl der Anfragen angibt. ($1 \le Q \le 10\,000$)

In den nächsten $Q$ Zeilen werden jeweils die ganzen Zahlen $t, x$ durch ein Leerzeichen getrennt gegeben. Dies stellt eine Anfrage nach dem Abstand von der Koordinate $x$ zum nächstgelegenen Fahrrad zum Zeitpunkt $t$ dar. ($0 \le t \le T$; $0 \le x \le 10^9$)

Es wird garantiert, dass in der gegebenen Eingabe jedes Fahrrad höchstens $K$ Fahrrädern begegnet.

Ausgabe

Gib für jede Anfrage die Antwort als gekürzten Bruch im Format $p / q$ jeweils in einer eigenen Zeile aus. Dabei ist $p$ eine nichtnegative ganze Zahl und $q$ eine positive ganze Zahl.

Beispiele

Eingabe 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

Ausgabe 1

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