Jaewon gikk en tur langs elven Gapcheon for å lufte tankene. Langs elvebredden går det en snorrett sykkelsti. På sykkelstien beveger $N$ sykler seg, hver med konstant hastighet.

La tidspunktet da Jaewon startet turen være $0$, og tidspunktet da han avsluttet turen være $T$. Koordinaten til den $i$-te sykkelen er $s_i$ da Jaewon startet turen, og $e_i$ da Jaewon avsluttet turen. For alle syklene er verdiene $s_i$ parvis forskjellige, og verdiene $e_i$ er også parvis forskjellige.

Mens Jaewon går tur, møter hver sykkel høyst $K$ andre sykler. To sykler regnes som å møte hverandre når koordinatene deres blir like.

Jaewon ønsker å beregne hva avstanden er fra en vilkårlig koordinat $x$ til den nærmeste sykkelen ved et vilkårlig tidspunkt $t$. Hjelp Jaewon med å løse $Q$ spørringer.

Inndata

På den første linjen gis heltallene $N, T, K$ adskilt med mellomrom. $N$ er antallet sykler, $T$ er tidspunktet da Jaewon avsluttet turen, og $K$ er den øvre grensen for hvor mange ganger hver sykkel møter andre sykler. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

På de neste $N$ linjene gis sykkelens startkoordinat $s_i$ og sluttkoordinat $e_i$ adskilt med mellomrom. ($0 \le s_i, e_i \le 10^9$) For alle $i$ er verdiene $s_i$ parvis forskjellige, og verdiene $e_i$ er også parvis forskjellige.

På neste linje gis et heltall $Q$ som angir antallet spørringer. ($1 \le Q \le 10\,000$)

På de neste $Q$ linjene gis heltallene $t, x$ adskilt med mellomrom. De representerer en spørring som spør om avstanden fra koordinaten $x$ til den nærmeste sykkelen ved tidspunkt $t$. ($0 \le t \le T$; $0 \le x \le 10^9$)

Det garanteres at hver sykkel i de gitte inndataene møter høyst $K$ sykler.

Utdata

For hver spørring skal du skrive ut svaret som en uforkortelig brøk på formen $p / q$, ett svar per linje, der $p$ er et ikke-negativt heltall og $q$ er et positivt heltall.

Eksempler

Inndata 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

Utdata 1

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