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>
const double eps = 1e-11;
const int maxn = 1010, maxm = 2010;
int n, m, u[maxm], v[maxm], a[maxm], b[maxm], c[maxm], d[maxm];
struct edge {
  int to;
  double cap;
  edge *rev, *next;
} E[maxm * 2 + maxn * 4], *ne, *fir[maxn], *cur[maxn];
void link(int a, int b, double c) {
  *ne = (edge){b, c, ne + 1, fir[a]};
  fir[a] = ne++;
  *ne = (edge){a, 0, ne - 1, fir[b]};
  fir[b] = ne++;
}
int Q[maxn], D[maxn];
double dfs(int i, double c) {
  if (i == 1 || c < eps) return c;
  double fl = 0, f;
  for (edge*& e = cur[i]; e && c >= eps; e = e->next)
    if (e->cap >= eps && D[e->to] == D[i] - 1)
      fl += f = dfs(e->to, c < e->cap ? c : e->cap), e->cap -= f,
            e->rev->cap += f, c -= f;
  return fl;
}
double mf() {
  for (double f = 0;; f += dfs(0, 1e18)) {
    for (int i = 0; i <= n + 1; i++) D[i] = 0, cur[i] = fir[i];
    for (int *h = Q, *t = Q + (D[*Q = 1] = 1); h < t; h++)
      for (edge* e = fir[*h]; e; e = e->next)
        if (e->rev->cap >= eps && !D[e->to]) D[*t++ = e->to] = D[*h] + 1;
    if (!*D) return f;
  }
}
int da[maxn];
double de[maxn];
int chk(double t) {
  ne = E;
  for (int i = 0; i <= n + 1; i++) fir[i] = 0, da[i] = 0, de[i] = 0;
  for (int i = 0; i < m; i++) {
    link(u[i] + 1, v[i] + 1, (c[i] - a[i]) * t + d[i] - b[i]);
    double x = a[i] * t + b[i];
    da[u[i]] -= a[i];
    da[v[i]] += a[i];
    de[u[i]] -= x;
    de[v[i]] += x;
  }
  double s = 0;
  for (int i = 1; i <= n; i++) {
    if (de[i] > 0)
      link(0, i + 1, de[i]), s += de[i];
    else
      link(i + 1, 1, -de[i]);
  }
  if (mf() < s - 1e-8) {
    int sa = 0;
    for (int i = 1; i <= n; i++) D[i + 1] ? sa += da[i] : 1;
    for (int i = 0; i < m; i++)
      !D[u[i] + 1] && D[v[i] + 1] ? sa += c[i] - a[i] : 1;
    return sa > 0 ? -1 : 1;
  }
  return 0;
}
double solve(double l, double r, int lv, int rv) {
  double mid;
  while (r - l > 1e-8) {
    int t = chk(mid = (l + r) / 2);
    if (t == lv)
      l = mid;
    else if (t == rv)
      r = mid;
    else
      return solve(mid, r, 0, 1) - solve(l, mid, -1, 0);
  }
  return lv < 0 && rv > 0 ? 0 : 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);
  printf("%.7lf\n", solve(0, 1, -1, 1));
}