Dice Attack Simulation

In the game "Dungeons and Dice," a player performs a guaranteed-hit attack by rolling Y dice, each of which is an X-sided die. Note that an X-sided die here is defined to have faces numbered from 0 to X - 1, each with equal probability \(\frac{1}{X}\). In other words, if a random variable \(W\) represents the number on a die, then

Moreover, the first moment (expectation) is given by

[ v_1(W)=E(W)=\frac{X-1}{2} ]

and the second central moment (variance) is

[ \mu_2(W)=E((W-E(W))^2)=\frac{X^2-1}{12} ]

Now, in a battle, the enemy has a health value of A and has no defense. A single guaranteed-hit attack is performed by rolling Y dice (i.e. employing the notation YdX), and the total damage is the sum of all dice displayed values. The enemy is defeated only if the damage is at least A. However, to avoid the scenario of overkill, the damage must not exceed B. Only when the damage lies in the interval [A, B] does the player score a victory.

Your task is to help by computing the probability that a random attack (as described) leads to victory.

inputFormat

The first line contains three integers Y, X and T, where Y is the number of dice, X is the number of sides for each die (the die shows numbers from 0 to X - 1), and T is the number of battle simulations.

Then T lines follow; each line contains two integers A and B, representing the enemy's health and the maximum damage allowed (to avoid overkill), respectively.

outputFormat

For each simulation, output the probability that the attack leads to a victory, i.e. the probability that the total damage (obtained by rolling Y dice) lies in the interval [A, B]. The answer should be printed as a floating‐point number with 6 decimal places, and each result should be output on a new line.

sample

1 6 3
2 4
0 5
5 5

0.500000
1.000000
0.166667