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>
template <typename Y>
inline bool updmin(Y &a, Y b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename Y>
inline bool updmax(Y &a, Y b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename Y>
inline Y abs(Y a) {
  if (a < 0) a = -a;
  return a;
}
template <typename Y>
inline Y sqr(Y a) {
  return a * a;
}
int read() {
  int w = 1, q = 0, ch = ' ';
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') w = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) q = q * 10 + ch - 48;
  return q * w;
}
inline void FileIO() {
  freopen(
      ""
      ".in",
      "r", stdin);
  freopen(
      ""
      ".out",
      "w", stdout);
}
const int maxn = 10080;
const long long M = 1e9;
int n, m, U[maxn], V[maxn];
long long a[maxn], b[maxn], c[maxn], d[maxn];
namespace fa {
const long long inf = 1ll << 60;
int e_num = 1, S, T;
int hed[maxn], dep[maxn];
long long deg[maxn];
struct Edge {
  int from, to, nxt;
  long long c;
} edge[maxn * 4];
void addedge(int from, int to, long long c) {
  edge[++e_num] = (Edge){from, to, hed[from], c};
  hed[from] = e_num;
}
void adde(int from, int to, long long c) {
  addedge(from, to, c);
  addedge(to, from, 0);
}
void clear() {
  e_num = 1;
  memset(hed, 0, sizeof hed);
}
std::queue<int> q;
bool bfs() {
  while (!q.empty()) {
    q.pop();
  }
  q.push(S);
  memset(dep, 0, sizeof(dep));
  dep[S] = 1;
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (int i = hed[cur]; i; i = edge[i].nxt) {
      int to = edge[i].to;
      if (!dep[to] && edge[i].c) {
        dep[to] = dep[cur] + 1;
        q.push(to);
      }
    }
  }
  return dep[T];
}
long long dfs(int x, long long flow) {
  if (x == T) return flow;
  long long ret = 0;
  for (int i = hed[x]; i; i = edge[i].nxt) {
    int to = edge[i].to;
    if (dep[to] == dep[x] + 1 && edge[i].c) {
      long long tmp = dfs(to, std::min(flow, edge[i].c));
      edge[i].c -= tmp;
      edge[i ^ 1].c += tmp;
      flow -= tmp;
      ret += tmp;
      if (!flow) {
        break;
      }
    }
  }
  if (!ret) dep[x] = 0;
  return ret;
}
long long dinic() {
  long long ret = 0;
  while (bfs()) {
    ret += dfs(S, inf);
  }
  return ret;
}
long long check(long long t) {
  long long suml = 0;
  clear();
  S = 0, T = n + 1;
  memset(deg, 0, sizeof deg);
  for (int i = 1; i <= m; i++) {
    long long l = a[i] * t + b[i];
    long long r = c[i] * t + d[i];
    deg[U[i]] -= l;
    deg[V[i]] += l;
    adde(U[i], V[i], r - l);
  }
  for (int i = 1; i <= n; i++) {
    if (deg[i] > 0) {
      suml += deg[i];
      adde(S, i, deg[i]);
    } else {
      adde(i, T, -deg[i]);
    }
  }
  long long d = dinic();
  return suml - d;
}
}  // namespace fa
long long L, R, ans1, ans2;
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= m; i++) {
    U[i] = read();
    V[i] = read();
    a[i] = read();
    b[i] = read() * M;
    c[i] = read();
    d[i] = read() * M;
  }
  L = 0, R = M;
  while (L < R) {
    long long mid = (L + R) >> 1;
    long long delta = fa::check(mid + 1) - fa::check(mid);
    if (delta >= 0) {
      R = mid;
    } else {
      L = mid + 1;
    }
  }
  ans1 = L;
  if (fa::check(ans1) != 0) {
    puts("0");
    return 0;
  }
  L = 0, R = M;
  while (L < R) {
    long long mid = (L + R + 1) >> 1;
    long long delta = fa::check(mid) - fa::check(mid - 1);
    if (delta <= 0) {
      L = mid;
    } else {
      R = mid - 1;
    }
  }
  ans2 = R;
  printf("%.10lf\n", (double)(ans2 - ans1) / (double)M);
  return 0;
}