Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Random Ranking

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputImagine a real contest or exam of *n* participants. Every participant will get a particular score. We can predict the standings board more or less, if we do some statistics on their previous performance.

Let's say the score of the participants will be uniformly distributed in interval [*l*_{i}, *r*_{i}] (the score can be a real number). Can you predict the standings board according to these data? In other words you should say for each participant the probability that he gets some fixed place in the scoreboard. The participants are sorted by increasing of their scores in the scoreboard. So, the participant with the largest score gets the last place.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 80), showing how many participants we have. Each of the next *n* lines contains our predictions, the *i*-th line contains a pair of integers *l*_{i}, *r*_{i} (0 ≤ *l*_{i} < *r*_{i} ≤ 10^{9}) as the distributed interval for participant *i*.

Consider the participants numbered from 1 to *n* in some way.

Output

Output a distributed matrix *a* of order *n*. The element *a*_{ij} of the matrix is the probability that participant *i* has rank *j*.

Your answer will considered correct if it has at most 10^{ - 6} absolute or relative error.

Examples

Input

2

1 6

4 9

Output

0.9200000000 0.080

0.080 0.9200000000

Input

8

0 2

1 3

2 4

3 5

4 6

5 7

6 8

7 9

Output

0.875 0.125 0 0 0 0 0 0

0.125 0.750 0.125 0 0 0 0 0

0 0.125 0.750 0.125 0 0 0 0

0 0 0.125 0.750 0.125 0 0 0

0 0 0 0.125 0.750 0.125 0 0

0 0 0 0 0.125 0.750 0.125 0

0 0 0 0 0 0.125 0.750 0.125

0 0 0 0 0 0 0.125 0.875

Note

The score probability distribution is continuous, which means, there is no possibility for a draw.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/24/2017 16:24:02 (c3).

Desktop version, switch to mobile version.
User lists

Name |
---|