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 = 50010;
const long long E = 1e7;
const long long INF = 1e18;
long long n, m, ct;
long long u[N], v[N], a[N], b[N], c[N], d[N];
long long hd[N], nxt[N], to[N], cp[N];
long long dst[N], que[N], cur[N];
long long head, tail;
void link(int u, int v, long long c) {
  to[++ct] = v;
  cp[ct] = c;
  nxt[ct] = hd[u];
  hd[u] = ct;
}
bool bfs() {
  for (int i = 0; i <= (n + 1); i++) dst[i] = 0;
  dst[0] = 1;
  head = 0, tail = 1;
  que[++head] = 0;
  while (head <= tail) {
    int u = que[head++];
    for (int i = hd[u]; i; i = nxt[i]) {
      int v = to[i];
      if (!dst[v] && cp[i] > 0) {
        dst[v] = dst[u] + 1;
        que[++tail] = v;
        if (v == (n + 1)) break;
      }
    }
  }
  return dst[(n + 1)];
}
long long dfs(long long u, long long f) {
  if (u == (n + 1) || f == 0) return f;
  long long vf = 0;
  for (long long &i = cur[u]; i; i = nxt[i]) {
    if (cp[i] > 0 && dst[to[i]] == dst[u] + 1) {
      long long fl = dfs(to[i], min(f, cp[i]));
      if (fl) {
        cp[i] -= fl;
        cp[i ^ 1] += fl;
        f -= fl;
        vf += fl;
        if (!f) break;
      }
    }
  }
  return vf;
}
long long dinic() {
  long long ret = 0;
  while (bfs()) {
    for (int i = 0; i <= (n + 1); i++) cur[i] = hd[i];
    while (long long f = dfs(0, INF)) ret += f;
  }
  return ret;
}
long long flow(long long x) {
  long long ret = 0;
  ct = 1;
  for (int i = 0; i <= (n + 1); i++) hd[i] = 0;
  for (int i = 1; i <= m; i++) {
    long long lb = a[i] * x + b[i], ub = c[i] * x + d[i];
    ret += lb;
    link(0, v[i], lb);
    link(v[i], 0, 0);
    link(u[i], (n + 1), lb);
    link((n + 1), u[i], 0);
    link(u[i], v[i], ub - lb);
    link(v[i], u[i], 0);
  }
  return ret - dinic();
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> u[i] >> v[i] >> a[i] >> b[i] >> c[i] >> d[i];
    b[i] *= E;
    d[i] *= E;
  }
  int l = 0, r = E;
  while (r - l >= 3) {
    int df = (r - l) / 3;
    if (flow(l + df) < flow(r - df))
      r -= df;
    else
      l += df;
  }
  long long mf = flow(l);
  for (int i = l + 1; i <= r; i++) {
    if (long long f = flow(i) < mf) {
      mf = f;
      l = i;
    }
  }
  if (mf > 0) return puts("0"), 0;
  int lp = 0, rp = l - 1;
  while (lp <= rp) {
    int m = (lp + rp) / 2;
    if (flow(m) > 0)
      lp = m + 1;
    else
      rp = m - 1;
  }
  long long ans = -lp;
  lp = l + 1, rp = E;
  while (lp <= rp) {
    int m = (lp + rp) / 2;
    if (flow(m) > 0)
      rp = m - 1;
    else
      lp = m + 1;
  }
  ans += rp;
  cout << fixed << setprecision(10) << (double)ans / E << endl;
  return 0;
}