Чжевон пішов прогулятися до річки Капчхон, щоб розвіятися. Уздовж берега річки по прямій прокладено велодоріжку. Велодоріжкою рухаються $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$. Вони позначають запит про відстань від координати $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