Description

Input

The first line contains a positive integer $n$ ($2 \leq n \leq 200$) — the number of points in $S$.

The $i$-th of the following $n$ lines contains two space-separated integers $x_i$ and $y_i$ ($-10^4 \leq x_i, y_i \leq 10^4$) — the coordinates of the $i$-th point in $S$. The input guarantees that for all $1 \leq i \lt j \leq n$, $(x_i, y_i) \neq (x_j, y_j)$ holds.

The next line contains a positive integer $q$ ($1 \leq q \leq 200$) — the number of queries.

Each of the following $q$ lines contains two space-separated integers $t$ and $m$ ($1 \leq t_i \leq n$, $1 \leq m_i \leq 10^4$) — the index of the target point and the number of moves, respectively.

Output

Output $q$ lines each containing a decimal number — the $i$-th among them denotes the maximum probability of staying on the $t_i$-th point after $m_i$ steps, with a proper choice of starting position $P$.

Your answer will be considered correct if each number in your output differs from the corresponding one in jury's answer by at most $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $|a - b| \le 10^{-6}$.

5
0 0
1 3
2 2
3 1
4 4
10
1 1
2 1
3 1
4 1
5 1
3 2
3 3
3 4
3 5
3 6

0.50000000000000000000
0.50000000000000000000
0.33333333333333331483
0.50000000000000000000
0.50000000000000000000
0.18518518518518517491
0.15226337448559670862
0.14494741655235482414
0.14332164812274550414
0.14296036624949901017

Note

The points in $S$ and possible candidates for line $l$ are depicted in the following figure.

For the first query, when $P = (-1, -3)$, $l$ is uniquely determined to be $3x = y$, and thus Kanno will move to $(0, 0)$ with a probability of $\frac 1 2$.

For the third query, when $P = (2, 2)$, $l$ is chosen equiprobably between $x + y = 4$ and $x = y$. Kanno will then move to the other four points with a probability of $\frac 1 2 \cdot \frac 1 3 = \frac 1 6$ each, or stay at $(2, 2)$ with a probability of $\frac 1 3$.