แจวอนออกไปเดินเล่นที่แม่น้ำคัพชอนเพื่อเปลี่ยนบรรยากาศ ที่แม่น้ำคัพชอนมีทางจักรยานทอดยาวเป็นเส้นตรงไปตามริมฝั่งแม่น้ำ บนทางจักรยานมีจักรยาน $N$ คันที่แต่ละคันกำลังเคลื่อนที่ด้วยความเร็วคงที่

ให้เวลาที่แจวอนเริ่มเดินเล่นเป็น $0$ และเวลาที่เดินเล่นเสร็จเป็น $T$ พิกัดของจักรยานคันที่ $i$ คือ $s_i$ เมื่อแจวอนเริ่มเดินเล่น และคือ $e_i$ เมื่อแจวอนเดินเล่นเสร็จ สำหรับจักรยานทุกคัน ค่า $s_i$ จะแตกต่างกันทั้งหมด และค่า $e_i$ ก็แตกต่างกันทั้งหมดเช่นกัน

ในระหว่างที่แจวอนเดินเล่น จักรยานแต่ละคันจะพบกับจักรยานคันอื่นไม่เกิน $K$ คัน เราถือว่าจักรยานสองคันพบกันเมื่อพิกัดของจักรยานทั้งสองคันเท่ากัน

แจวอนต้องการคำนวณว่าระยะทางจากพิกัด $x$ ใด ๆ ไปยังจักรยานที่อยู่ใกล้ที่สุดในเวลา $t$ ใด ๆ มีค่าเท่าใด มาช่วยแจวอนตอบคำถาม $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$ คั่นด้วยช่องว่าง แทนคำถามที่ถามหาระยะทางจากพิกัด $x$ ไปยังจักรยานที่อยู่ใกล้ที่สุดในเวลา $t$ ($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