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 int N = 1e3 + 10, M = 2e3 + 10, D = N, E = 1e5 + 10;
int n, m, S, T;
struct QAQ {
  int x, y, a, b, c, d;
} q[M];
struct Edge {
  int to, nxt;
  long double cap;
} e[E];
int cnt, lnk[D], mn[D], level[D];
long double sum[D];
bool bfs() {
  queue<int> q;
  memset(level, 0x3f, sizeof(level));
  q.push(S);
  level[S] = 1;
  while (q.size()) {
    int x = q.front();
    q.pop();
    for (int i = lnk[x]; i; i = e[i].nxt) {
      int y = e[i].to;
      if (e[i].cap > 1e-9 && level[y] > level[x] + 1) {
        level[y] = level[x] + 1;
        q.push(y);
      }
    }
  }
  return level[T] < 1e9;
}
long double dinic(int x, long double f) {
  if (x == T) return f;
  long double used = 0;
  for (int i = lnk[x]; i; i = e[i].nxt)
    if (e[i].cap > 1e-9 && level[e[i].to] == level[x] + 1) {
      long double w = dinic(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;
}
void adde(int x, int y, long double c) {
  e[++cnt] = (Edge){y, lnk[x], c}, lnk[x] = cnt;
  e[++cnt] = (Edge){x, lnk[y], 0}, lnk[y] = cnt;
}
long double chk(long double t) {
  cnt = 1;
  memset(lnk, 0, sizeof(lnk));
  memset(sum, 0, sizeof(sum));
  for (int i = 1; i <= m; i++) {
    long double l = q[i].a * t + q[i].b, r = q[i].c * t + q[i].d;
    adde(q[i].x, q[i].y, r - l);
    sum[q[i].x] -= l, sum[q[i].y] += l;
  }
  long double tot = 0;
  for (int i = 1; i <= n; i++) {
    if (sum[i] > 0)
      adde(S, i, sum[i]), tot += sum[i];
    else
      adde(i, T, -sum[i]);
  }
  while (bfs()) tot -= dinic(S, 1e9);
  return tot;
}
int main() {
  cin >> n >> m;
  S = 0, T = 1001;
  for (int i = 1; i <= m; i++) {
    int x, y, a, b, c, d;
    scanf("%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
    q[i] = (QAQ){x, y, a, b, c, d};
  }
  long double top = -1, l = 0, r = 1;
  for (int i = 1; i <= 50; i++) {
    long double lmid = l + (r - l) / 3, rmid = lmid + (r - l) / 3;
    long double lans = chk(lmid), rans = chk(rmid);
    if (lans < 1e-9) {
      top = lmid;
      break;
    }
    if (rans < 1e-9) {
      top = rmid;
      break;
    }
    if (lans < rans)
      r = rmid;
    else
      l = lmid;
  }
  if (top < 0) return puts("0"), 0;
  long double L = top, R = top;
  l = 0, r = top;
  for (int i = 1; i <= 50; i++) {
    long double mid = (l + r) * 0.5;
    if (chk(mid) < 1e-9)
      L = mid, r = mid;
    else
      l = mid;
  }
  l = top, r = 1;
  for (int i = 1; i <= 50; i++) {
    long double mid = (l + r) * 0.5;
    if (chk(mid) < 1e-9)
      R = mid, l = mid;
    else
      r = mid;
  }
  printf("%.10lf\n", (double)(R - L));
  return 0;
}