E. Случайное распределение рангов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Представим настоящий контест или экзамен, состоящий из n участников. Каждый участник получит определенное количество очков. Мы можем более-менее предсказать состояние турнирной таблицы, если рассчитаем статистику прошлых успехов участников.

Предположим, что очки i-ого участника будут равномерно распределены по интервалу [li, ri] (очки участника могут быть вещественным числом). Можете ли Вы предсказать состояние турнирной таблицы по этим данным? Другими словами, для каждого участника Вы должны найти вероятность того, что он займет в итоговой таблице определенное место. Участники в таблице сортируются по возрастанию очков, то есть участник с наибольшим количеством очков занимает последнее место.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 80), показывающее, сколько у нас участников. Каждая из следующих n строк содержит наши предсказания, i-ая строка содержит пару целых чисел li, ri (0 ≤ li < ri ≤ 109) — интервал очков участника i.

Считайте участников пронумерованными некоторым образом от 1 до n.

Выходные данные

Выведите квадратную матрицу a порядка n. Элемент aij матрицы — это вероятность того, что участник i получит место j.

Ваш ответ будет засчитан, если абсолютная или относительная ошибка не превышает 10 - 6.

Примеры
Входные данные
2
1 6
4 9
Выходные данные
0.9200000000 0.080 
0.080 0.9200000000
Входные данные
8
0 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
Выходные данные
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
Примечание

Вероятностное распределение очков непрерывное. Это значит, что ничья невозможна.