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;
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
const long long maxn = 2007, maxm = 4007, inf = 0x3f3f3f3f3f3f3f3f;
long long n, m, s, t, maxflow;
long long dep[maxn], cur[maxn], de[maxn];
long long tot = 1, head[maxn];
struct edge {
  long long to, nxt, w;
} e[maxm << 1];
inline void adde(long long u, long long v, long long w) {
  e[++tot] = (edge){v, head[u], w};
  head[u] = tot;
}
inline void add(long long u, long long v, long long w) {
  adde(u, v, w);
  adde(v, u, 0);
}
inline void ins(long long u, long long v, long long l, long long r) {
  add(u, v, r - l), de[u] -= l, de[v] += l;
}
bool bfs(long long s, long long t) {
  queue<long long> q;
  memcpy(cur, head, sizeof cur);
  memset(dep, 63, sizeof dep);
  dep[s] = 0;
  q.push(s);
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    for (long long i = head[u]; i; i = e[i].nxt) {
      long long v = e[i].to;
      if (dep[v] == inf && e[i].w) {
        dep[v] = dep[u] + 1;
        q.push(v);
      }
    }
  }
  return dep[t] < inf;
}
long long dfs(long long u, long long t, long long minn) {
  if (!minn || u == t) return minn;
  long long res = 0;
  for (long long i = cur[u]; i; i = e[i].nxt) {
    long long v = e[i].to;
    cur[u] = i;
    if (dep[v] != dep[u] + 1) continue;
    long long flow = dfs(v, t, min(minn, e[i].w));
    if (!flow) continue;
    res += flow, minn -= flow;
    e[i].w -= flow, e[i ^ 1].w += flow;
    if (!minn) break;
  }
  if (!res) dep[u] = 0;
  return res;
}
inline long long dinic(long long s, long long t) {
  long long maxflow = 0;
  while (bfs(s, t)) maxflow += dfs(s, t, inf);
  return maxflow;
}
long long a[maxn], b[maxn], c[maxn], d[maxn], uu[maxn], vv[maxn],
    lim = 100000000;
map<long long, long long> mp;
long long func(long long v) {
  if (mp.count(v)) return mp[v];
  for (register long long i = (1); i <= (n + 2); ++i) head[i] = de[i] = 0;
  s = n + 1, t = n + 2;
  tot = 1;
  for (register long long i = (1); i <= (m); ++i) {
    long long l = a[i] * v + b[i] * lim, r = c[i] * v + d[i] * lim;
    ins(uu[i], vv[i], l, r);
  }
  long long res = 0;
  for (register long long i = (1); i <= (n); ++i)
    if (de[i] > 0)
      add(s, i, de[i]), res += de[i];
    else
      add(i, t, -de[i]);
  return mp[v] = res - dinic(s, t);
}
signed main() {
  n = read(), m = read();
  for (register long long i = (1); i <= (m); ++i) {
    uu[i] = read(), vv[i] = read();
    a[i] = read(), b[i] = read(), c[i] = read(), d[i] = read();
  }
  func(75000004);
  long long l = 0, r = lim;
  while (r - l >= 5) {
    long long m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
    if (func(m1) < func(m2))
      r = m2;
    else
      l = m1;
  }
  pair<long long, long long> mg = make_pair(inf, inf);
  for (register long long i = (l); i <= (r); ++i)
    mg = min(mg, make_pair(func(i), i));
  if (mg.first) {
    puts("0");
    return 0;
  }
  l = mg.second + 1, r = lim;
  long long resl = mg.second, resr = mg.second;
  while (l <= r) {
    long long mid = l + r >> 1;
    if (!func(mid))
      resr = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  l = 0, r = mg.second - 1;
  while (l <= r) {
    long long mid = l + r >> 1;
    if (!func(mid))
      resl = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%.8lf", 1.0 * (resr - resl) / lim);
  return 0;
}