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;
const long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
const double EPS = 1e-9;
const double inf = 1e20;
inline int sign(double a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(double a, double b) { return sign(a - b); }
const int N = 101000;
int ts, u[N], v[N], a[N], b[N], c[N], d[N], n, m;
namespace flow {
const int M = 101000, N = 101000;
int y[M], nxt[M], gap[N], fst[N], c[N], pre[N], q[N], dis[N];
int slope[M];
double f[M];
int S, T, tot, Tn;
void init(int s, int t, int tn) {
  tot = 1;
  memset(fst, 0, sizeof(fst));
  S = s;
  T = t;
  Tn = tn;
}
void add(int u, int v, int c, double c1, double c2 = 0) {
  tot++;
  y[tot] = v;
  f[tot] = c1;
  nxt[tot] = fst[u];
  fst[u] = tot;
  slope[tot] = c;
  tot++;
  y[tot] = u;
  f[tot] = c2;
  nxt[tot] = fst[v];
  fst[v] = tot;
  slope[tot] = 0;
}
double sap() {
  int u = S, t = 1;
  double flow = 0;
  for (int i = 0; i < Tn; i++) c[i] = fst[i], dis[i] = Tn, gap[i] = 0;
  q[0] = T;
  dis[T] = 0;
  pre[S] = 0;
  for (int i = 0; i < t; i++) {
    int u = q[i];
    for (int j = fst[u]; j; j = nxt[j])
      if (dis[y[j]] > dis[u] + 1 && fabs(f[j ^ 1]) > EPS)
        q[t++] = y[j], dis[y[j]] = dis[u] + 1;
  }
  for (int i = 0; i < Tn; i++) gap[dis[i]]++;
  while (dis[S] <= Tn) {
    while (c[u] && (fabs(f[c[u]]) < EPS || dis[y[c[u]]] + 1 != dis[u]))
      c[u] = nxt[c[u]];
    if (c[u]) {
      pre[y[c[u]]] = c[u] ^ 1;
      u = y[c[u]];
      if (u == T) {
        double minf = inf;
        for (int p = pre[T]; p; p = pre[y[p]]) minf = min(minf, f[p ^ 1]);
        for (int p = pre[T]; p; p = pre[y[p]]) f[p ^ 1] -= minf, f[p] += minf;
        flow += minf;
        u = S;
      }
    } else {
      if (!(--gap[dis[u]])) break;
      int mind = Tn;
      c[u] = fst[u];
      for (int j = fst[u]; j; j = nxt[j])
        if (fabs(f[j]) > EPS && dis[y[j]] < mind) mind = dis[y[j]], c[u] = j;
      dis[u] = mind + 1;
      gap[dis[u]]++;
      if (u != S) u = y[pre[u]];
    }
  }
  q[0] = S;
  t = 1;
  for (int i = 0; i < Tn; i++) dis[i] = Tn;
  dis[S] = 0;
  for (int i = 0; i < t; i++) {
    int u = q[i];
    for (int j = fst[u]; j; j = nxt[j])
      if (dis[y[j]] > dis[u] + 1 && fabs(f[j]) > EPS) {
        dis[y[j]] = dis[u] + 1;
        q[t++] = y[j];
      }
  }
  ts = 0;
  for (int i = 0; i < Tn; i++)
    for (int j = fst[i]; j; j = nxt[j])
      if (dis[i] < Tn && dis[y[j]] >= Tn) ts += slope[j];
  return flow;
}
};  // namespace flow
double bel[N];
int sl[N];
int check(double t) {
  for (int i = 1; i < n + 1; i++) bel[i] = 0, sl[i] = 0;
  flow::init(0, n + 1, n + 2);
  for (int i = 0; i < m; i++) {
    double l = a[i] * t + b[i], r = c[i] * t + d[i];
    flow::add(u[i], v[i], c[i] - a[i], r - l);
    bel[u[i]] += l;
    bel[v[i]] -= l;
    sl[u[i]] += a[i];
    sl[v[i]] -= a[i];
  }
  double sf = 0;
  int ss = 0;
  for (int i = 1; i < n + 1; i++)
    if (bel[i] > 0) {
      sf += bel[i];
      flow::add(i, n + 1, sl[i], bel[i]);
      ss += sl[i];
    } else
      flow::add(0, i, -sl[i], -bel[i]);
  double r = flow::sap();
  if (ts == ss) {
    if (cmp(r, sf) == -1)
      return 2;
    else
      return 1;
  } else if (ts > ss)
    return 0;
  else
    return 2;
}
double gao(int ty) {
  double l = 0, r = 1;
  for (int it = 0; it < 30; it++) {
    double md = (l + r) * 0.5;
    if (check(md) >= ty)
      r = md;
    else
      l = md;
  }
  return 0.5 * (l + r);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++)
    scanf("%d%d%d%d%d%d", u + i, v + i, a + i, b + i, c + i, d + i);
  double l = gao(1), r = gao(2);
  printf("%.10f\n", r - l);
}