Jaewon est allé se promener le long de la rivière Gapcheon pour se changer les idées. Une piste cyclable rectiligne longe la rive. Sur cette piste cyclable, $N$ vélos se déplacent chacun à vitesse constante.

Soit $0$ l'instant où Jaewon commence sa promenade et $T$ l'instant où il la termine. La coordonnée du $i$-ème vélo est $s_i$ lorsque Jaewon commence sa promenade, et $e_i$ lorsqu'il la termine. Pour tous les vélos, les valeurs $s_i$ sont deux à deux distinctes, et les valeurs $e_i$ sont également deux à deux distinctes.

Pendant la promenade de Jaewon, chaque vélo rencontre au plus $K$ autres vélos. On considère que deux vélos se rencontrent lorsque leurs coordonnées deviennent égales.

Jaewon souhaite calculer la distance entre une coordonnée arbitraire $x$ et le vélo le plus proche à un instant arbitraire $t$. Aidez Jaewon à répondre à $Q$ requêtes.

Entrée

La première ligne contient trois entiers $N, T, K$ séparés par des espaces. $N$ est le nombre de vélos, $T$ est l'instant où Jaewon termine sa promenade, et $K$ est la borne supérieure du nombre d'autres vélos que chaque vélo rencontre. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

Chacune des $N$ lignes suivantes contient la coordonnée initiale $s_i$ et la coordonnée finale $e_i$ d'un vélo, séparées par un espace. ($0 \le s_i, e_i \le 10^9$) Pour tout $i$, les valeurs $s_i$ sont deux à deux distinctes, et les valeurs $e_i$ sont également deux à deux distinctes.

La ligne suivante contient un entier $Q$ représentant le nombre de requêtes. ($1 \le Q \le 10\,000$)

Chacune des $Q$ lignes suivantes contient deux entiers $t, x$ séparés par un espace, représentant une requête demandant la distance entre la coordonnée $x$ et le vélo le plus proche à l'instant $t$. ($0 \le t \le T$; $0 \le x \le 10^9$)

Il est garanti que, dans l'entrée donnée, chaque vélo rencontre au plus $K$ autres vélos.

Sortie

Pour chaque requête, affichez la réponse sous la forme d'une fraction irréductible $p / q$, à raison d'une par ligne, où $p$ est un entier naturel et $q$ est un entier strictement positif.

Exemples

Entrée 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

Sortie 1

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