O. Average Range Query Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The $$$n$$$ CodeCode problem testers each solved all $$$t$$$ problems on the contest! Each problem tester gives feedback by giving a range of numbers $$$[l_i, r_i]$$$ for the difficulty. From each range a random real number is selected. What is the expected value of the range of the final numbers that are chosen for each problem?

A range of a set of values is the maximum difference between any two values.

Input

The first line contains two integers $$$n$$$ and $$$t$$$ ($$$n \le 200$$$, $$$t \le 10$$$), the number of problem testers who gave feedback and number of problems, respectively. The description of each test case follows.

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 3500$$$)— the ranges of difficulty for the problem.

Output

Print $$$t$$$ lines, each with the expected value of the range of the final dataset of the difficulties. Round your answer to the nearest ten thousandth.

To round in C, you can use printf("%.4lf", var);

To round in C++, you can use std::cout«std::fixed«std::setprecision(4)«var«endl;

To round in Python, you can use round(var, 4)

Example
Input
3 3
900 900
800 1000
1000 1100
800 800
3300 3500
0 3500
800 800
0 3500
3499 3500
Output
175.0000
2693.3333
2790.9286
Note

For the first test case, there are two possibilities:

While the first problem tester gives a difficulty of $$$900$$$, the second problem tester gives a lower difficulty from $$$800$$$ to $$$900$$$. The third problem tester gives a difficulty from $$$1000$$$ to $$$1100$$$. The expected value of the range is $$$200$$$.

The first problem tester gives the difficulty $$$900$$$. The second problem tester gives a difficulty from $$$900$$$ to $$$1000$$$. The third problem tester gives a difficulty from $$$1000$$$ to $$$1100$$$. The expected value of the range is $$$150$$$.

Since these two happen with equal probability, the expected value of the range is $$$175$$$.

 —

Problem Idea: thehunterjames

Problem Preparation: thehunterjames, codicon

Occurrences: Advanced $$$8$$$