Jaewon lähti kävelylle Gapcheon-joelle virkistäytyäkseen. Joen rantaa pitkin kulkee viivasuora pyörätie. Pyörätiellä liikkuu $N$ polkupyörää, joista jokainen etenee tasaisella nopeudella.

Olkoon ajanhetki, jolloin Jaewon aloitti kävelyn, $0$, ja ajanhetki, jolloin hän lopetti kävelyn, $T$. $i$-nnen polkupyörän koordinaatti on $s_i$, kun Jaewon aloitti kävelyn, ja $e_i$, kun Jaewon lopetti kävelyn. Kaikille polkupyörille arvot $s_i$ ovat keskenään erisuuria, ja myös arvot $e_i$ ovat keskenään erisuuria.

Jaewonin kävelyn aikana jokainen polkupyörä kohtaa korkeintaan $K$ muuta polkupyörää. Kahden polkupyörän katsotaan kohtaavan toisensa, kun niiden koordinaateista tulee yhtä suuret.

Jaewon halusi laskea, kuinka suuri on etäisyys mielivaltaisesta koordinaatista $x$ lähimpään polkupyörään mielivaltaisella ajanhetkellä $t$. Auta Jaewonia ratkaisemaan $Q$ kyselyä.

Syöte

Ensimmäisellä rivillä annetaan välilyönnein erotettuina kokonaisluvut $N, T, K$. $N$ on polkupyörien lukumäärä, $T$ on ajanhetki, jolloin Jaewon lopetti kävelyn, ja $K$ on yläraja sille, kuinka monta kertaa kukin polkupyörä kohtaa muita polkupyöriä. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

Seuraavilla $N$ rivillä annetaan välilyönnillä erotettuina polkupyörän alkukoordinaatti $s_i$ ja loppukoordinaatti $e_i$. ($0 \le s_i, e_i \le 10^9$) Kaikilla $i$ arvot $s_i$ ovat keskenään erisuuria, ja myös arvot $e_i$ ovat keskenään erisuuria.

Seuraavalla rivillä annetaan kyselyiden lukumäärää kuvaava kokonaisluku $Q$. ($1 \le Q \le 10\,000$)

Seuraavilla $Q$ rivillä annetaan välilyönnillä erotettuina kokonaisluvut $t, x$. Ne kuvaavat kyselyä, jossa kysytään etäisyyttä koordinaatista $x$ lähimpään polkupyörään ajanhetkellä $t$. ($0 \le t \le T$; $0 \le x \le 10^9$)

Annetussa syötteessä taataan, että jokainen polkupyörä kohtaa korkeintaan $K$ polkupyörää.

Tuloste

Tulosta jokaiseen kyselyyn vastaus supistetussa murtolukumuodossa $p / q$ omalle rivilleen, missä $p$ on epänegatiivinen kokonaisluku ja $q$ on positiivinen kokonaisluku.

Esimerkit

Syöte 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

Tuloste 1

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