Чжэвон көңіл сергіту үшін Капчхон өзеніне серуендеуге барды. Капчхон өзенінің жағалауын бойлай түзу сызықпен веложол салынған. Веложолда $N$ велосипед әрқайсысы тұрақты жылдамдықпен қозғалып келеді.

Чжэвон серуенді бастаған уақыт мезетін $0$, ал серуенді аяқтаған уақыт мезетін $T$ деп алайық. $i$-ші велосипедтің координатасы Чжэвон серуенді бастаған кезде $s_i$, ал серуенді аяқтаған кезде $e_i$ болады. Барлық велосипедтер үшін $s_i$ мәндері өзара әртүрлі, сондай-ақ $e_i$ мәндері де өзара әртүрлі.

Чжэвон серуендеп жүрген уақытта әрбір велосипед көп дегенде $K$ басқа велосипедті ғана кездестіреді. Екі велосипедтің координаталары теңескен кезде олар бір-бірін кездестірді деп есептеледі.

Чжэвон кез келген $t$ уақыт мезетінде кез келген $x$ координатасынан ең жақын велосипедке дейінгі арақашықтық қанша екенін есептегісі келді. Чжэвонға $Q$ сұранымды шешуге көмектесіңіз.

Кіріс деректер

Бірінші жолда бос орын арқылы бөлінген $N, T, K$ бүтін сандары беріледі. $N$ — велосипедтер саны, $T$ — Чжэвон серуенді аяқтаған уақыт мезеті, ал $K$ — әр велосипедтің басқа велосипедтерді кездестіру санының жоғарғы шегі. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

Келесі $N$ жолда бос орын арқылы бөлінген велосипедтің бастапқы координатасы $s_i$ мен соңғы координатасы $e_i$ беріледі. ($0 \le s_i, e_i \le 10^9$) Барлық $i$ үшін $s_i$ мәндері өзара әртүрлі, сондай-ақ $e_i$ мәндері де өзара әртүрлі.

Келесі жолда сұранымдар санын білдіретін $Q$ бүтін саны беріледі. ($1 \le Q \le 10\,000$)

Келесі $Q$ жолда бос орын арқылы бөлінген $t, x$ бүтін сандары беріледі. Олар $t$ уақыт мезетінде $x$ координатасынан ең жақын велосипедке дейінгі арақашықтықты сұрайтын сұранымды білдіреді. ($0 \le t \le T$; $0 \le x \le 10^9$)

Берілген кіріс деректерде әрбір велосипед көп дегенде $K$ велосипедті кездестіретініне кепілдік беріледі.

Шығыс деректер

Әрбір сұранымға жауапты қысқартылмайтын бөлшек $p / q$ түрінде әр жолға біреуден шығарыңыз, мұндағы $p$ — теріс емес бүтін сан, ал $q$ — оң бүтін сан.

Мысалдар

Кіріс деректер 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

Шығыс деректер 1

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