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 int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
long double d[1001 + 5], in[1001 + 5];
int n, m, q[1001 + 5], head[1001 + 5], cnt, top, c[1001 + 5];
struct Edge {
  int u, v, a, b, c, d;
} s[2000 + 5];
struct edge {
  int to, next;
  long double cap;
} e[100005];
inline void ins(int f, int t, long double w) {
  e[++cnt] = (edge){t, head[f], w};
  head[f] = cnt;
  e[++cnt] = (edge){f, head[t], 0};
  head[t] = cnt;
}
bool bfs() {
  for (int i = 1; i <= 1001; ++i) d[i] = 1e9;
  int i, j;
  for (d[q[top = i = 1] = 0] = 0; i <= top; ++i)
    for (j = c[q[i]] = head[q[i]]; j; j = e[j].next)
      if (e[j].cap > 1e-9 && d[q[i]] + 1 < d[e[j].to])
        d[q[++top] = e[j].to] = d[q[i]] + 1;
  return d[1001] < 1e8;
}
long double dfs(int x, long double f) {
  if (x == 1001) return f;
  long double used = 0;
  for (int& i = c[x]; i; i = e[i].next)
    if (e[i].cap > 1e-9 && d[e[i].to] == d[x] + 1) {
      long double w = dfs(e[i].to, min(f - used, e[i].cap));
      used += w;
      e[i].cap -= w;
      e[i ^ 1].cap += w;
      if (f - used < 1e-9) return f;
    }
  return used;
}
long double Solve(long double t) {
  cnt = 1;
  memset(head, 0, sizeof(head));
  memset(in, 0, sizeof(in));
  for (int i = 1; i <= m; ++i) {
    long double l = t * s[i].a + s[i].b, r = t * s[i].c + s[i].d;
    ins(s[i].u, s[i].v, r - l);
    in[s[i].u] -= l;
    in[s[i].v] += l;
  }
  long double res = 0;
  for (int i = 1; i <= n; ++i)
    if (in[i] > 0)
      res += in[i], ins(0, i, in[i]);
    else
      ins(i, 1001, -in[i]);
  while (bfs()) res -= dfs(0, 1e9);
  return res;
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= m; ++i)
    s[i].u = read(), s[i].v = read(), s[i].a = read(), s[i].b = read(),
    s[i].c = read(), s[i].d = read();
  long double l = 0, r = 1, ok = -1;
  while (r - l > 1e-9) {
    long double m1 = l + (r - l) / 3, m2 = m1 + (r - l) / 3;
    long double r1 = Solve(m1), r2 = Solve(m2);
    if (r1 < 1e-9) {
      ok = m1;
      break;
    }
    if (r2 < 1e-9) {
      ok = m2;
      break;
    }
    if (r1 < r2)
      r = m2;
    else
      l = m1;
  }
  if (ok < 0) return 0 * puts("0");
  l = 0, r = ok;
  long double L = ok, R = ok;
  while (r - l > 1e-9) {
    long double mid = (l + r) * 0.5;
    if (Solve(mid) < 1e-9)
      L = mid, r = mid;
    else
      l = mid;
  }
  l = ok;
  r = 1;
  while (r - l > 1e-9) {
    long double mid = (l + r) * 0.5;
    if (Solve(mid) < 1e-9)
      R = mid, l = mid;
    else
      r = mid;
  }
  printf("%.10lf\n", (double)(R - L));
  return 0;
}