The Strange Galton Board

Francis Galton invented the Galton board to demonstrate the central limit theorem: that for a large enough sample size, the binomial distribution approaches the normal distribution. A Galton board consists of a board with pegs set perpendicular to it. When a marble is dropped from the top, it repeatedly hits rows of pegs and bounces either left or right. Marbles that reach the bottom are separated by partitions, and an ordinary Galton board shows a normal distribution as in the figure above. In the strange Galton board of the strange land, however, a marble lands on every destination reachable from its starting point with equal probability. Because a similar number of marbles at every destination would be boring, the starting point from which the marble is dropped can be chosen.

For a strange Galton board of height 5, the numbering of starting points and destinations follows the rule shown above.

If a marble is dropped from starting point 2, it reaches every destination in [1, 5] with equal probability. If it is dropped from starting point 6, it reaches every destination in [3, 6] with equal probability.

Alice of the strange land dropped marbles onto the strange Galton board and tried to count the marbles at the destinations, but there were too many and she gave up. Instead she wants to estimate the counts by computing the expected number of marbles at the destinations. Help Alice by writing a program that outputs the expected values of the marbles.

The program performs two kinds of queries.

$Q$ queries that drop marbles are given.

$a$, $b$: $b$ marbles are dropped from the $a$-th starting point.

After all marbles have been dropped, $R$ queries ask for the expected number of marbles at the destinations.

$a, b$: Output the expected number of marbles that land on destinations [$a, b$].

The program terminates after processing all expectation queries.

The first line gives the height $H$. ($1 \le H \le 100,000$)

The second line gives the number of marble-dropping queries $Q$ and the number of expectation queries $R$. ($1 \le Q \le 100,000$, $1 \le R \le 100,000$)

Starting from the third line, $Q$ queries $a, b$ are given. ($1 \le a \le \frac{H(H + 1)}{2}$, $1 \le b \le 100,000$)

Starting from line 3 + $Q$, $R$ queries $a$, $b$ are given. ($1 \le a \le b \le H + 1$)

Output the result of each query in order, one per line.

Absolute or relative error up to $10^{-4}$ is allowed.