Problem: Imagine 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.

<image>

Let's say the score of the participants will be uniformly distributed in interval [li, ri] (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 li, ri (0 ≤ li < ri ≤ 109) 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 aij 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.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Locale;
import java.util.Random;
import java.util.StringTokenizer;

import static java.lang.Math.max;
import static java.lang.Math.min;

import static java.util.Arrays.deepToString;

public class E {
	final static Random rng = new Random(58);
	final static boolean debug = false;
	static int n, from, to;
	static int[] left, right;
	static double[][] tmp;
	static double[][][] res;
	static double[][][][] allD;
	static int op = 0;

	static void addSinglePlayer(double[][] d, int who, int done) {
		double len = right[who] - left[who];
		double downD = min(1, max(0, right[who] - to) / len);
		double upD = min(1, max(0, from - left[who]) / len);
		double hereD = (1 - upD - downD);
		for (int up = 0; up <= done + 1; up++) {
			d[up][done + 1 - up] = 0;
		}
		for (int up = done; up >= 0; up--) {
			for (int here = done - up; here >= 0; here--) {
				double p = d[up][here];
				d[up + 1][here] += p * upD;
				d[up][here + 1] += p * hereD;
				d[up][here] = p * downD;
			}
		}
	}

	static double[][] addTo(double[][] d, int from, int to, int done) {
		if (allD[from][to] == null) {
			int sz = done + to - from + 2;
			allD[from][to] = new double[sz][sz];
			for (int i = 0; i < sz; i++) {
				allD[from][to][i] = new double[sz - i];
			}
		}
		double[][] nd = allD[from][to];
		for (int i = 0; i < d.length; i++)
			System.arraycopy(d[i], 0, nd[i], 0, d[i].length);
		for (int who = from; who <= to; who++) {
			addSinglePlayer(nd, who, done++);
		}
		return nd;
	}

	static void calcAll(double[][] d, int from, int to, int done) {
		if (from == to) {
			calcFor(from, d);
			return;
		}
		int mid = (from + to) >> 1;
		double[][] dForRight = addTo(d, from, mid, done);
		calcAll(dForRight, mid + 1, to, done + (mid - from + 1));
		double[][] dForLeft = addTo(d, mid + 1, to, done);
		calcAll(dForLeft, from, mid, done + (to - mid));
	}

	static void calcFor(int player, double[][] d) {
		if (from >= right[player] || to <= left[player])
			return;
		double c = (to - from) * 1D / (right[player] - left[player]);
		for (int up = 0; up < n; up++) {
			for (int here = 0; here < n - up; here++) {
				res[player][up][here] += d[up][here] * c / (here + 1);
			}
		}
	}

	static void solve() {
		n = debug ? 80 : nextInt();
		left = new int[n];
		right = new int[n];
		ArrayList<Integer> all = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			left[i] = debug ? rng.nextInt((int) 1e8) : nextInt();
			right[i] = debug ? left[i] + rng.nextInt((int) 1e8) : nextInt();
			all.add(left[i]);
			all.add(right[i]);
		}
		Collections.sort(all);
		tmp = new double[n + 1][n + 1];
		res = new double[n][n][n];
		allD = new double[n][n][][];

		for (int i = 0; i < all.size() - 1; i++) {
			from = all.get(i);
			to = all.get(i + 1);
			double[][] init = new double[][] { new double[] { 1, 0 }, new double[] { 0 } };
			calcAll(init, 0, n - 1, 0);
		}
		double[][] ans = new double[n][n];
		for (int player = 0; player < n; player++) {
			for (int up = 0; up < n; up++) {
				for (int here = 0; here < n - up; here++) {
					for (int choose = 0; choose <= here; choose++) {
						ans[player][up + choose] += res[player][up][here];
					}
				}
			}
		}
		if (!debug) {
			for (double[] vA : ans) {
				for (double v : vA) {
					writer.print(v + " ");
				}
				writer.println();
			}
		}
	}

	public static void main(String[] args) throws Exception {
		reader = new BufferedReader(new InputStreamReader(System.in));
		writer = new PrintWriter(System.out);
		Locale.setDefault(Locale.US);

		setTime();
		solve();
		printTime();
		printMemory();

		writer.close();
	}

	static BufferedReader reader;
	static PrintWriter writer;
	static StringTokenizer tok = new StringTokenizer("");
	static long systemTime;

	static void debug(Object... o) {
		System.err.println(deepToString(o));
	}

	static void setTime() {
		systemTime = System.currentTimeMillis();
	}

	static void printTime() {
		System.err.println("Time consumed: " + (System.currentTimeMillis() - systemTime));
	}

	static void printMemory() {
		System.err.println("Memory consumed: "
				+ (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / 1000 + "kb");
	}

	static String next() {
		while (!tok.hasMoreTokens()) {
			String w = null;
			try {
				w = reader.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			if (w == null)
				return null;
			tok = new StringTokenizer(w);
		}
		return tok.nextToken();
	}

	static int nextInt() {
		return Integer.parseInt(next());
	}

	static long nextLong() {
		return Long.parseLong(next());
	}

	static double nextDouble() {
		return Double.parseDouble(next());
	}

	static BigInteger nextBigInteger() {
		return new BigInteger(next());
	}
}