Jaewon pergi berjalan-jalan di sepanjang Sungai Gapcheon untuk menyegarkan pikiran. Sebuah jalur sepeda lurus membentang di sepanjang tepi sungai. Terdapat $N$ sepeda yang bergerak di sepanjang jalur sepeda tersebut, masing-masing dengan kecepatan konstan.

Misalkan waktu ketika Jaewon mulai berjalan-jalan adalah $0$, dan waktu ketika ia selesai berjalan-jalan adalah $T$. Koordinat sepeda ke-$i$ adalah $s_i$ ketika Jaewon mulai berjalan-jalan dan $e_i$ ketika ia selesai berjalan-jalan. Untuk semua sepeda, nilai $s_i$ saling berbeda, dan nilai $e_i$ juga saling berbeda.

Selama Jaewon berjalan-jalan, setiap sepeda bertemu dengan paling banyak $K$ sepeda lainnya. Dua sepeda dianggap bertemu ketika koordinat mereka menjadi sama.

Jaewon ingin menghitung berapa jarak dari suatu koordinat $x$ sembarang ke sepeda terdekat pada suatu waktu $t$ sembarang. Bantulah Jaewon menyelesaikan $Q$ kueri.

Masukan

Baris pertama berisi tiga bilangan bulat $N, T, K$ yang dipisahkan oleh spasi. $N$ adalah jumlah sepeda, $T$ adalah waktu ketika Jaewon selesai berjalan-jalan, dan $K$ adalah batas atas jumlah sepeda lain yang ditemui oleh masing-masing sepeda. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

Masing-masing dari $N$ baris berikutnya berisi koordinat awal $s_i$ dan koordinat akhir $e_i$ dari sepeda, dipisahkan oleh spasi. ($0 \le s_i, e_i \le 10^9$) Untuk semua $i$, nilai $s_i$ saling berbeda, dan nilai $e_i$ juga saling berbeda.

Baris berikutnya berisi sebuah bilangan bulat $Q$ yang menyatakan jumlah kueri. ($1 \le Q \le 10\,000$)

Masing-masing dari $Q$ baris berikutnya berisi dua bilangan bulat $t, x$ yang dipisahkan oleh spasi, yang menyatakan kueri yang menanyakan jarak dari koordinat $x$ ke sepeda terdekat pada waktu $t$. ($0 \le t \le T$; $0 \le x \le 10^9$)

Dijamin bahwa pada masukan yang diberikan, setiap sepeda bertemu dengan paling banyak $K$ sepeda lainnya.

Keluaran

Untuk setiap kueri, cetak jawaban dalam bentuk pecahan paling sederhana $p / q$, satu per baris, di mana $p$ adalah bilangan bulat tak negatif dan $q$ adalah bilangan bulat positif.

Contoh

Masukan 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

Keluaran 1

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