Jaewon went for a walk along the Gapcheon River to refresh himself. A straight bike path runs along the riverbank. There are $N$ bicycles traveling along the bike path, each at a constant velocity.

Let the time when Jaewon starts his walk be $0$, and the time when he finishes his walk be $T$. The position of the $i$-th bicycle is $s_i$ when Jaewon starts his walk and $e_i$ when he finishes it. The values $s_i$ are pairwise distinct, and the values $e_i$ are also pairwise distinct.

During Jaewon's walk, each bicycle meets at most $K$ other bicycles. Two bicycles are considered to meet when their positions become equal.

Jaewon wants to calculate the distance from an arbitrary position $x$ to the nearest bicycle at an arbitrary time $t$. Help Jaewon answer $Q$ queries.

Input

The first line contains three integers $N, T, K$, separated by spaces. $N$ is the number of bicycles, $T$ is the time when Jaewon finishes his walk, and $K$ is the upper bound on the number of other bicycles that each bicycle meets. ($1 \le N \le 1\,000\,000$; $1 \le T \le 10^9$; $1 \le K \le 1\,000$)

Each of the next $N$ lines contains two integers $s_i$ and $e_i$, the initial and final positions of the bicycle, separated by a space. ($0 \le s_i, e_i \le 10^9$) For all $i$, the values $s_i$ are pairwise distinct, and the values $e_i$ are also pairwise distinct.

The next line contains an integer $Q$, the number of queries. ($1 \le Q \le 10\,000$)

Each of the next $Q$ lines contains two integers $t, x$, separated by a space, representing a query asking for the distance from position $x$ to the nearest bicycle at time $t$. ($0 \le t \le T$; $0 \le x \le 10^9$)

It is guaranteed that, in the given input, each bicycle meets at most $K$ other bicycles.

Output

For each query, print the answer on a separate line as an irreducible fraction in the form $p / q$, where $p$ is a nonnegative integer and $q$ is a positive integer.

Examples

Input 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

Output 1

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