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;
int fst[666666], nxt[666666], vb[666666], ff[666666], M = 1, N = 0;
long long cap[666666];
void _ad_dl(int a, int b, long long c) {
  ++M;
  nxt[M] = fst[a];
  fst[a] = M;
  vb[M] = b;
  cap[M] = c;
}
void ad_dl(int a, int b, long long c) {
  _ad_dl(a, b, c);
  _ad_dl(b, a, 0);
}
int S, T, q[666666], d_[666666];
bool bfs() {
  memset(d_, -1, 4 * (N + 1));
  d_[T] = 0;
  q[1] = T;
  int h = 1, t = 2;
  while (h != t) {
    int cur = q[h++];
    for (int e = fst[cur]; e; e = nxt[e]) {
      int b = vb[e];
      if (d_[b] == -1 && cap[e ^ 1]) {
        d_[b] = d_[cur] + 1, q[t++] = b;
        if (b == S) return 1;
      }
    }
  }
  return d_[S] != -1;
}
long long dfs(int x, long long f) {
  if (f <= 0) return 0;
  if (x == T) return f;
  long long ca = 0;
  for (int& e = fst[x]; e; e = nxt[e]) {
    int b = vb[e];
    if (d_[b] + 1 != d_[x]) continue;
    long long w = dfs(b, (cap[e] < f - ca) ? cap[e] : (f - ca));
    cap[e] -= w;
    cap[e ^ 1] += w;
    ca += w;
    if (ca == f) break;
  }
  if (!ca) d_[x] = -1;
  return ca;
}
long long dinic() {
  long long ans = 0;
  memcpy(ff, fst, 4 * (N + 1));
  while (bfs()) ans += dfs(S, 2e18), memcpy(fst, ff, 4 * (N + 1));
  return ans;
}
const long long G = 1.01e7;
int n, e, u[666666], v[666666], a[666666], b[666666], c[666666], d[666666];
long long ds[666666];
long long f(long long x) {
  for (int i = 1; i <= N; ++i) fst[i] = ds[i] = 0;
  N = n;
  S = ++N;
  T = ++N;
  M = 1;
  for (int i = 1; i <= e; ++i) {
    long long L = a[i] * x + b[i] * G, R = c[i] * x + d[i] * G;
    ad_dl(u[i], v[i], R - L);
    ds[v[i]] += L;
    ds[u[i]] -= L;
  }
  long long sb = 0;
  for (int i = 1; i <= N; ++i)
    if (ds[i] > 0)
      ad_dl(S, i, ds[i]), sb += ds[i];
    else if (ds[i] < 0)
      ad_dl(i, T, -ds[i]);
  long long aa = sb - dinic();
  return aa;
}
int main() {
  cin >> n >> e;
  for (int i = 1; i <= e; ++i)
    cin >> u[i] >> v[i] >> a[i] >> b[i] >> c[i] >> d[i];
  long long l = 0, r = G;
  while (r - l > 10) {
    long long m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
    if (f(m1) < f(m2))
      r = m2;
    else
      l = m1;
  }
  pair<long long, long long> mi(8e18, 8e18);
  for (long long t = l; t <= r; ++t) mi = min(mi, make_pair(f(t), t));
  if (mi.first) {
    puts("0");
    return 0;
  }
  l = mi.second, r = G;
  while (l < r) {
    long long m = (l + r + 1) >> 1;
    if (f(m))
      r = m - 1;
    else
      l = m;
  }
  long long ans = l;
  l = 0, r = mi.second;
  while (l < r) {
    long long m = (l + r) >> 1;
    if (f(m))
      l = m + 1;
    else
      r = m;
  }
  ans -= l;
  printf("%.10lf\n", ans / double(G));
}