Problem: Vova has recently learned what a circulaton in a graph is. Recall the definition: let G = (V, E) be a directed graph. A circulation f is such a collection of non-negative real numbers f_e (e ∈ E), that for each vertex v ∈ V the following conservation condition holds:

$$$∑_{e ∈ \delta^{-}(v)} f_e = ∑_{e ∈ \delta^{+}(v)} f_e$$$

where \delta^{+}(v) is the set of edges that end in the vertex v, and \delta^{-}(v) is the set of edges that start in the vertex v. In other words, for each vertex the total incoming flow should be equal to the total outcoming flow.

Let a lr-circulation be such a circulation f that for each edge the condition l_e ≤ f_e ≤ r_e holds, where l_e and r_e for each edge e ∈ E are two non-negative real numbers denoting the lower and upper bounds on the value of the circulation on this edge e.

Vova can't stop thinking about applications of a new topic. Right now he thinks about the following natural question: let the graph be fixed, and each value l_e and r_e be a linear function of a real variable t:

$$$l_e(t) = a_e t + b_e r_e(t) = c_e t + d_e$$$

Note that t is the same for all edges.

Let t be chosen at random from uniform distribution on a segment [0, 1]. What is the probability of existence of lr-circulation in the graph?

Input

The first line contains two integers n, m (1 ≤ n ≤ 1000, 1 ≤ m ≤ 2000).

Each of the next m lines describes edges of the graph in the format u_e, v_e, a_e, b_e, c_e, d_e (1 ≤ u_e, v_e ≤ n, -10^4 ≤ a_e, c_e ≤ 10^4, 0 ≤ b_e, d_e ≤ 10^4), where u_e and v_e are the startpoint and the endpoint of the edge e, and the remaining 4 integers describe the linear functions for the upper and lower bound of circulation.

It is guaranteed that for any t ∈ [0, 1] and for any edge e ∈ E the following condition holds 0 ≤ l_e(t) ≤ r_e(t) ≤ 10^4.

Output

Print a single real integer — the probability of existence of lr-circulation in the graph, given that t is chosen uniformly at random from the segment [0, 1]. Your answer is considered correct if its absolute difference from jury's answer is not greater than 10^{-6}.

Example

Input

3 3
1 2 0 3 -4 7
2 3 -2 5 1 6
3 1 0 4 0 4


Output

0.25

Note

In the first example the conservation condition allows only circulations with equal values f_e for all three edges. The value of circulation on the last edge should be 4 whatever t is chosen, so the probability is

$$$P(4 ∈ [3, -4t + 7]~~\&~~4 ∈ [-2t + 5, t + 6]) = 0.25$$$

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 1000;
const int MAXM = 2000;
struct E {
  int from, to, al, bl, ar, br;
  double l, r;
};
const int GMAXN = MAXN + 2;
const int GMAXM = 2 * MAXN + MAXM;
const double eps = 1e-12;
struct G {
  int n, m;
  int ghead[GMAXN], gnxt[2 * GMAXM], gto[2 * GMAXM];
  double gcap[2 * GMAXM];
  int level[GMAXN];
  int q[GMAXN], qhead, qtail;
  int gcur[GMAXN];
  int path[GMAXN], npath;
  bool incut[2 * GMAXM];
  void init(int _n) {
    n = _n, m = 0;
    for (int i = (0); i < (n); ++i) ghead[i] = -1;
  }
  int addedge(int a, int b, double cap) {
    int ret = m;
    gnxt[m] = ghead[a], ghead[a] = m, gto[m] = b, gcap[m] = cap;
    ++m;
    gnxt[m] = ghead[b], ghead[b] = m, gto[m] = a, gcap[m] = 0;
    ++m;
    return ret;
  }
  bool calclevel(int s, int t) {
    for (int i = (0); i < (n); ++i) level[i] = -1;
    qhead = qtail = 0;
    level[s] = 0, q[qhead++] = s;
    while (qtail < qhead) {
      int at = q[qtail++];
      for (int x = ghead[at]; x != -1; x = gnxt[x])
        if (gcap[x] >= eps) {
          int to = gto[x];
          if (level[to] == -1) level[to] = level[at] + 1, q[qhead++] = to;
        }
    }
    return level[t] != -1;
  }
  bool augment(int at, int t, double lim, double &flow) {
    if (at == t) {
      flow = lim;
      path[npath++] = at;
      return true;
    }
    for (; gcur[at] != -1; gcur[at] = gnxt[gcur[at]]) {
      int x = gcur[at], to = gto[x];
      if (gcap[x] < eps || level[to] != level[at] + 1) continue;
      if (augment(to, t, min(lim, gcap[x]), flow)) {
        gcap[x] -= flow;
        gcap[x ^ 1] += flow;
        path[npath++] = at;
        return true;
      }
    }
    return false;
  }
  double maxflow(int s, int t) {
    double ret = 0;
    while (calclevel(s, t)) {
      for (int i = (0); i < (n); ++i) gcur[i] = ghead[i];
      while (true) {
        double cur;
        npath = 0;
        if (!augment(s, t, 1e200, cur)) break;
        ret += cur;
      }
    }
    return ret;
  }
  void calccut(int s, int t) {
    assert(!calclevel(s, t));
    for (int i = (0); i < (m); ++i) incut[i] = false;
    for (int at = (0); at < (n); ++at)
      if (level[at] >= 0)
        for (int x = ghead[at]; x != -1; x = gnxt[x])
          if (level[gto[x]] == -1) incut[x] = true;
  }
};
int n, m;
E e[MAXM];
G g;
double insum[MAXN], outsum[MAXN];
int inid[MAXN], outid[MAXN], eid[MAXM];
void findcut(double t, int &acut, int &bcut) {
  for (int i = (0); i < (m); ++i)
    e[i].l = e[i].al * t + e[i].bl, e[i].r = e[i].ar * t + e[i].br;
  for (int i = (0); i < (n); ++i) insum[i] = outsum[i] = 0;
  for (int i = (0); i < (m); ++i)
    outsum[e[i].from] += e[i].l, insum[e[i].to] += e[i].l;
  g.init(n + 2);
  int src = n, dst = n + 1;
  for (int i = (0); i < (n); ++i)
    inid[i] = insum[i] != 0 ? g.addedge(src, i, insum[i]) : -1;
  for (int i = (0); i < (n); ++i)
    outid[i] = outsum[i] != 0 ? g.addedge(i, dst, outsum[i]) : -1;
  for (int i = (0); i < (m); ++i)
    eid[i] =
        e[i].l < e[i].r ? g.addedge(e[i].from, e[i].to, e[i].r - e[i].l) : -1;
  g.maxflow(src, dst);
  g.calccut(src, dst);
  acut = bcut = 0;
  for (int i = (0); i < (m); ++i) acut -= e[i].al, bcut -= e[i].bl;
  for (int i = (0); i < (m); ++i) {
    if (eid[i] != -1 && g.incut[eid[i]])
      acut += e[i].ar - e[i].al, bcut += e[i].br - e[i].bl;
    if (outid[e[i].from] != -1 && g.incut[outid[e[i].from]])
      acut += e[i].al, bcut += e[i].bl;
    if (inid[e[i].to] != -1 && g.incut[inid[e[i].to]])
      acut += e[i].al, bcut += e[i].bl;
  }
}
bool findnonneg(double &tres) {
  double l = 0, r = 1;
  for (int rep = (0); rep < (100); ++rep) {
    if (l > r) return false;
    double m = l + (r - l) / 2;
    int a, b;
    findcut(m, a, b);
    if (a > 0) {
      if (a * m + b >= 0) {
        tres = m;
        return true;
      }
      double nl = -1.0 * b / a;
      assert(nl > l);
      l = nl;
    } else if (a < 0) {
      if (a * m + b >= 0) {
        tres = m;
        return true;
      }
      double nr = -1.0 * b / a;
      assert(nr < r);
      r = nr;
    } else {
      if (b >= 0) {
        tres = m;
        return true;
      }
      return false;
    }
  }
  printf("err: %.15lf..%15lf\n", l, r);
  return false;
}
double findtmn(double tok) {
  double l = 0, r = tok;
  for (int rep = (0); rep < (100); ++rep) {
    if (r - l < 1e-7) break;
    double m = l + (r - l) / 2;
    int a, b;
    findcut(m, a, b);
    if (a * m + b >= 0) {
      r = m;
    } else {
      assert(a > 0);
      double nl = -1.0 * b / a;
      assert(nl > l);
      l = nl;
    }
  }
  return r;
}
double findtmx(double tok) {
  double l = tok, r = 1;
  for (int rep = (0); rep < (100); ++rep) {
    if (r - l < 1e-7) break;
    double m = l + (r - l) / 2;
    int a, b;
    findcut(m, a, b);
    if (a * m + b >= 0) {
      l = m;
    } else {
      assert(a < 0);
      double nr = -1.0 * b / a;
      assert(nr < r);
      r = nr;
    }
  }
  return l;
}
void run() {
  scanf("%d%d", &n, &m);
  for (int i = (0); i < (m); ++i)
    scanf("%d%d%d%d%d%d", &e[i].from, &e[i].to, &e[i].al, &e[i].bl, &e[i].ar,
          &e[i].br),
        --e[i].from, --e[i].to;
  double tnonneg;
  if (!findnonneg(tnonneg)) {
    printf("0\n");
    return;
  }
  double tmn = findtmn(tnonneg);
  double tmx = findtmx(tnonneg);
  printf("%.15lf\n", tmx - tmn);
}
int main() {
  run();
  return 0;
}