Xiao R has purchased $n$ light bulbs produced by different manufacturers. The lifespan of these light bulbs is a random variable. The shelf life of the $i$-th light bulb is $T_i$, and the bulb will not fail during its shelf life. After the shelf life, the lifespan of the bulb follows an exponential distribution with parameter $\lambda_i$. Formally, let $f_i(t)$ be the probability that the lifespan of the $i$-th bulb is greater than $t$, then

$$f_i(t)= \begin{cases} 1&t \le T_i\\ e^{-\lambda_i(t-T_i)}&t > T_i \end{cases}$$

where $1 \leq \lambda_i \leq 5$, $\lambda_i$ is an integer, and $0 \leq T_i < 1$.

Xiao R has made several independent predictions regarding the ranking of the light bulbs' lifespans. Each prediction specifies that the lifespan of bulb $i$ ranks $j$-th among all bulbs (ranked from longest to shortest, 1-indexed).

Please calculate the probability that each prediction is correct.

Input

The first line contains an integer $n$, representing the number of light bulbs.

The next $n$ lines each contain two real numbers $T_i$ and $\lambda_i$, representing the technical parameters of the $i$-th bulb.

The next line contains an integer $m$, representing the number of predictions.

The next $m$ lines each contain two integers $i$ and $j$, representing a prediction.

Output

For each prediction, output a single real number on a new line, representing the probability that the prediction is correct. Your answer is considered correct if and only if the relative or absolute error between your output and the standard output is no more than 1e-6.

Examples

Input 1

5
0.514 1
0.530 1
0.996 4
0.605 5
0.532 1
10
4 2
1 2
1 3
4 1
3 3
2 3
2 5
1 3
2 4
3 4

Output 1

0.040098
0.203478
0.169303
0.010344
0.356894
0.172687
0.163215
0.169303
0.170862
0.153489

Input 2

3
0.899 1
0.905 1
0.616 1
5
2 3
1 1
2 3
1 3
3 3

Output 2

0.248177
0.372920
0.248177
0.252671
0.499152

Input 3

See sample data download.

Subtasks

Note

This problem may encounter significant precision errors under certain extreme data conditions; however, the data for this problem is randomized, so those extreme cases can be ignored.