Jaewon fór í göngutúr meðfram Gapcheon-ánni til að hressa sig við. Meðfram árbakkanum liggur hjólreiðastígur í beinni línu. Á hjólreiðastígnum eru $N$ reiðhjól á ferð, hvert á jöfnum hraða.

Látum tímamarkið þegar Jaewon hóf göngutúrinn vera $0$ og tímamarkið þegar hann lauk göngutúrnum vera $T$. Hnit $i$-ta reiðhjólsins er $s_i$ þegar Jaewon hóf göngutúrinn og $e_i$ þegar Jaewon lauk göngutúrnum. Fyrir öll reiðhjól eru gildin $s_i$ innbyrðis ólík, og gildin $e_i$ eru einnig innbyrðis ólík.

Á meðan Jaewon er í göngutúrnum mætir hvert reiðhjól í mesta lagi $K$ öðrum reiðhjólum. Talað er um að tvö reiðhjól mætist þegar hnit þeirra verða jöfn.

Jaewon langaði að reikna út hver fjarlægðin er frá handahófskenndu hniti $x$ að næsta reiðhjóli á handahófskenndu tímamarki $t$. Hjálpaðu Jaewon að leysa $Q$ fyrirspurnir.

Inntak

Í fyrstu línunni eru gefnar heiltölurnar $N, T, K$ aðskildar með bilum. $N$ er fjöldi reiðhjóla, $T$ er tímamarkið þegar Jaewon lauk göngutúrnum og $K$ er efra mark á fjölda skipta sem hvert reiðhjól mætir öðrum reiðhjólum. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

Í næstu $N$ línum eru gefin upphafshnit $s_i$ og lokahnit $e_i$ reiðhjólsins aðskilin með bili. ($0 \le s_i, e_i \le 10^9$) Fyrir öll $i$ eru gildin $s_i$ innbyrðis ólík, og gildin $e_i$ eru einnig innbyrðis ólík.

Í næstu línu er gefin heiltala $Q$ sem táknar fjölda fyrirspurna. ($1 \le Q \le 10\,000$)

Í næstu $Q$ línum eru gefnar heiltölurnar $t, x$ aðskildar með bili. Þær tákna fyrirspurn sem spyr um fjarlægðina frá hnitinu $x$ að næsta reiðhjóli á tímamarkinu $t$. ($0 \le t \le T$; $0 \le x \le 10^9$)

Tryggt er að í gefnu inntaki mætir hvert reiðhjól í mesta lagi $K$ reiðhjólum.

Úttak

Fyrir hverja fyrirspurn skal prenta svarið sem óstyttanlegt brot á sniðinu $p / q$, eitt í hverri línu, þar sem $p$ er ekki-neikvæð heiltala og $q$ er jákvæð heiltala.

Dæmi

Inntak 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

Úttak 1

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