J. Playing with intervals
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ana and Beto created a game using intervals of integers. The game starts with an interval from $$$A$$$ to $$$B$$$ ($$$A \lt B$$$). On each move, the current player must choose either to increase the value of $$$A$$$ by one or decrease the value of $$$B$$$ by one. Ana makes the first move, Beto makes the second, Ana the third, and so on, alternating turns.

There are also $$$N$$$ special intervals of integers that influence the game. Beto's goal is to score as many points as possible by making the current interval $$$[A, B]$$$ become equal to one of these $$$N$$$ special intervals immediately after his move. In that case, the game ends and Beto earns a number of points equal to the size of the interval, that is, $$$B - A$$$ points.

On the other hand, Ana's goal is to minimize the number of points Beto earns. If at any point, after either player's move, the values of $$$A$$$ and $$$B$$$ become equal, the game ends and Beto earns 0 points.

Note that if $$$[A, B]$$$ becomes equal to one of the special intervals after Ana's move, or if the initial interval is already equal to a special interval, the game does not end and play continues normally.

For example, suppose the only special interval is $$$[1,2]$$$ and the game starts with $$$[A,B]=[0,3]$$$. On her first move, Ana may transform the interval into either $$$[1,3]$$$ or $$$[0,2]$$$. In both cases, Beto can then make the interval equal to $$$[1,2]$$$ on his next move and earn 1 point.

If the initial interval is $$$[0,2]$$$, $$$[1,3]$$$, or $$$[1,2]$$$, then in all of these cases the game ends with Beto earning 0 points.

Assuming Ana and Beto both play optimally, they would like your help answering the following question: given a positive integer $$$K$$$, if an initial interval $$$[A,B]$$$ is chosen uniformly at random among all intervals satisfying $$$0 \leq A \lt B \leq K$$$, what is the expected number of points Beto earns?

In other words, compute the arithmetic mean of the outcomes over all possible initial intervals.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq K \leq 10^6$$$).

The next $$$N$$$ lines each contain two integers $$$X_i$$$ and $$$Y_i$$$, representing one of the $$$N$$$ distinct special intervals $$$[X_i, Y_i]$$$ ($$$0 \leq X_i \lt Y_i \leq K$$$).

Output

Your program must output a single line containing two non-negative coprime integers $$$P$$$ and $$$Q$$$ such that $$$\frac{P}{Q}$$$ is equal to the expected number of points Beto earns in the game when the initial interval $$$[A,B]$$$ is chosen uniformly at random among all intervals satisfying $$$0 \leq A \lt B \leq K$$$.

That is, every interval meeting these conditions is equally likely to be selected, and $$$\frac{P}{Q}$$$ must represent the expected score in lowest terms.

Examples
Input
1 3
1 2
Output
1 6
Input
3 10
4 8
2 8
7 9
Output
24 55
Note

Explanation of Sample 1:

There are 6 possible starting intervals: $$$[0,1]$$$, $$$[0,2]$$$, $$$[0,3]$$$, $$$[1,2]$$$, $$$[1,3]$$$, and $$$[2,3]$$$. Beto earns 1 point only when the game starts with $$$[0,3]$$$. Therefore, the answer is $$$\frac{1}{6}$$$.