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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1},  {0, -1},
                        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <class T>
inline T max1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a > b ? a : b;
  if (c != -1234567) ans = max1(ans, c);
  if (d != -1234567) ans = max1(ans, d);
  return ans;
}
template <class T>
inline T min1(T a, T b, T c = -1234567, T d = -1234567) {
  T ans = a < b ? a : b;
  if (c != -1234567) ans = min(ans, c);
  if (d != -1234567) ans = min(ans, d);
  return ans;
}
template <class T>
inline T gcd1(T a, T b) {
  if (a < b) swap(a, b);
  if (a % b == 0) return b;
  return gcd1(b, a % b);
}
template <class T>
inline T lb(T num) {
  return num & (-num);
}
inline int jud(double a, double b) {
  if (abs1(a - b) < eps) return 0;
  if (a < b) return -1;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 1) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1 && be != 0) be--;
    if (!f_small && jud(*(a + be), val) == -1 && be != na - 1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1 && be != 0) be--;
    if (f_small && jud(*(a + be), val) == 1 && be != na - 1) be++;
  }
  return be;
}
inline int bitnum(unsigned long long nValue) {
  nValue = ((0xaaaaaaaaaaaaaaaaull & nValue) >> 1) +
           (0x5555555555555555ull & nValue);
  nValue = ((0xccccccccccccccccull & nValue) >> 2) +
           (0x3333333333333333ull & nValue);
  nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue) >> 4) +
           (0x0f0f0f0f0f0f0f0full & nValue);
  nValue = ((0xff00ff00ff00ff00ull & nValue) >> 8) +
           (0x00ff00ff00ff00ffull & nValue);
  nValue = ((0xffff0000ffff0000ull & nValue) >> 16) +
           (0x0000ffff0000ffffull & nValue);
  nValue = ((0xffffffff00000000ull & nValue) >> 32) +
           (0x00000000ffffffffull & nValue);
  return nValue;
}
long long pow(long long n, long long m, long long mod = 0) {
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
const int maxn = 82;
struct node {
  int l, r, mid, sum;
  double dp[maxn][maxn];
} stdp[10];
int n, lstdp;
int trans[maxn * 3], ltrans;
int orig[maxn][2];
double ans[maxn][maxn], p[maxn][3];
double rem[maxn][maxn][maxn];
int who[maxn], lwho, small;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", orig[i], orig[i] + 1);
    trans[i * 2] = orig[i][0];
    trans[i * 2 + 1] = orig[i][1];
  }
  sort(trans, trans + n * 2);
  ltrans = 1;
  for (int i = 1; i < n * 2; i++) {
    if (trans[i] != trans[i - 1]) trans[ltrans++] = trans[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < ltrans; j++)
      if (orig[i][0] == trans[j]) {
        orig[i][0] = j;
        break;
      }
    for (int j = 0; j < ltrans; j++)
      if (orig[i][1] == trans[j]) {
        orig[i][1] = j;
        break;
      }
  }
  memset(ans, 0, sizeof(ans));
  for (int i = 0; i < ltrans; i++) {
    lwho = 0, small = 0;
    for (int j = 0; j < n; j++)
      if (orig[j][0] <= i) {
        if (orig[j][1] > i) {
          who[lwho] = j;
          p[lwho][0] = double(trans[i] - trans[orig[j][0]]) /
                       (trans[orig[j][1]] - trans[orig[j][0]]);
          p[lwho][1] = double(trans[i + 1] - trans[i]) /
                       (trans[orig[j][1]] - trans[orig[j][0]]);
          p[lwho][2] = 1.0 - p[lwho][0] - p[lwho][1];
          lwho++;
        } else
          small++;
      }
    lstdp = 1;
    stdp[0].l = 0;
    stdp[0].r = lwho;
    stdp[0].mid = (stdp[0].l + stdp[0].r + 1) / 2;
    stdp[0].sum = 0;
    stdp[0].dp[0][0] = 1;
    for (int j = 0; j < lwho; j++) {
      for (;;) {
        if (stdp[lstdp - 1].r <= j) {
          lstdp--;
          continue;
        }
        if (stdp[lstdp - 1].l == stdp[lstdp - 1].r - 1) break;
        for (int i1 = 0; i1 <= lwho; i1++)
          for (int j1 = 0; j1 <= i1; j1++)
            stdp[lstdp].dp[j1][i1 - j1] = stdp[lstdp - 1].dp[j1][i1 - j1];
        if (stdp[lstdp - 1].mid <= j) {
          stdp[lstdp].l = stdp[lstdp - 1].mid;
          stdp[lstdp].r = stdp[lstdp - 1].r;
          stdp[lstdp].mid = (stdp[lstdp].l + stdp[lstdp].r + 1) / 2;
          stdp[lstdp].sum =
              stdp[lstdp - 1].sum + stdp[lstdp - 1].mid - stdp[lstdp - 1].l;
          for (int i1 = stdp[lstdp - 1].l; i1 < stdp[lstdp - 1].mid; i1++) {
            for (int j1 = stdp[lstdp].sum; j1 >= 0; j1--)
              for (int t1 = 0; t1 <= j1; t1++) {
                stdp[lstdp].dp[t1 + 1][j1 - t1] +=
                    stdp[lstdp].dp[t1][j1 - t1] * p[i1][0];
                stdp[lstdp].dp[t1][j1 - t1 + 1] +=
                    stdp[lstdp].dp[t1][j1 - t1] * p[i1][1];
                stdp[lstdp].dp[t1][j1 - t1] =
                    stdp[lstdp].dp[t1][j1 - t1] * p[i1][2];
              }
          }
        } else {
          stdp[lstdp].l = stdp[lstdp - 1].l;
          stdp[lstdp].r = stdp[lstdp - 1].mid;
          stdp[lstdp].mid = (stdp[lstdp].l + stdp[lstdp].r + 1) / 2;
          stdp[lstdp].sum =
              stdp[lstdp - 1].sum + stdp[lstdp - 1].r - stdp[lstdp - 1].mid;
          for (int i1 = stdp[lstdp - 1].mid; i1 < stdp[lstdp - 1].r; i1++) {
            for (int j1 = stdp[lstdp].sum; j1 >= 0; j1--)
              for (int t1 = 0; t1 <= j1; t1++) {
                stdp[lstdp].dp[t1 + 1][j1 - t1] +=
                    stdp[lstdp].dp[t1][j1 - t1] * p[i1][0];
                stdp[lstdp].dp[t1][j1 - t1 + 1] +=
                    stdp[lstdp].dp[t1][j1 - t1] * p[i1][1];
                stdp[lstdp].dp[t1][j1 - t1] =
                    stdp[lstdp].dp[t1][j1 - t1] * p[i1][2];
              }
          }
        }
        lstdp++;
      }
      for (int i1 = 0; i1 <= stdp[lstdp - 1].sum; i1++)
        for (int j1 = 0; j1 <= i1; j1++)
          rem[who[j]][j1 + small][i1 - j1] +=
              stdp[lstdp - 1].dp[j1][i1 - j1] * p[j][1];
    }
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k <= j; k++)
        for (int t = 0; t <= k; t++)
          ans[i][j - k + t] += rem[i][j - k][k] / (k + 1);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) printf("%.10lf ", ans[i][j]);
    printf("\n");
  }
  return 0;
}