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;
namespace Dinic {
const long long INF = 1LL << 60;
const int N = 1100;
const int M = 11000;
int fst[N], nxt[M], to[M];
long long cap[M];
int dis[N], q[N], ptr[N];
int V, E;
void init() {
  memset(fst, -1, sizeof fst);
  V = E = 0;
}
inline int add_node() {
  V++;
  return V - 1;
}
inline void add_edge(int u, int v, long long c) {
  to[E] = v, cap[E] = c, nxt[E] = fst[u], fst[u] = E++;
  to[E] = u, cap[E] = 0, nxt[E] = fst[v], fst[v] = E++;
}
inline bool bfs(int S, int T, int n) {
  memset(dis, -1, sizeof(int) * n);
  int h = 0, t = 0;
  dis[S] = 0, q[t++] = S;
  while (h < t) {
    int u = q[h++];
    for (int e = fst[u]; ~e; e = nxt[e])
      if (cap[e] > 0 && dis[to[e]] == -1) {
        dis[to[e]] = dis[u] + 1, q[t++] = to[e];
        if (to[e] == T) return 1;
      }
  }
  return (dis[T] != -1);
}
long long dfs(int u, int T, long long f) {
  if (u == T) return f;
  for (int &e = ptr[u]; ~e; e = nxt[e])
    if (cap[e] > 0 && dis[to[e]] > dis[u]) {
      long long ret = dfs(to[e], T, min(f, cap[e]));
      if (ret > 0) {
        cap[e] -= ret, cap[e ^ 1] += ret;
        return ret;
      }
    }
  return 0;
}
long long max_flow(int S, int T, int n = V) {
  long long ret = 0;
  while (bfs(S, T, n)) {
    memcpy(ptr, fst, sizeof(int) * n);
    for (long long cur; (cur = dfs(S, T, INF)) > 0; ret += cur)
      ;
  }
  return ret;
}
}  // namespace Dinic
long long ssum[1100], tsum[1100];
int n, m;
const int D = 10000000;
struct Edge {
  int u, v, a, b, c, d;
  void input() { scanf("%d%d%d%d%d%d", &u, &v, &a, &b, &c, &d); }
} e[2200];
long long calc(int mid) {
  Dinic::init();
  for (int i = 1; i <= n; i++) ssum[i] = tsum[i] = 0;
  for (int i = 1; i <= m; i++) {
    int u = e[i].u, v = e[i].v;
    long long l = e[i].a * 1LL * mid + e[i].b * 1LL * D;
    long long r = e[i].c * 1LL * mid + e[i].d * 1LL * D;
    ssum[v] += l, tsum[u] += l;
    Dinic::add_edge(u, v, r - l);
  }
  for (int i = 1; i <= n; i++) {
    if (ssum[i]) Dinic::add_edge(0, i, ssum[i]);
    if (tsum[i]) Dinic::add_edge(i, n + 1, tsum[i]);
  }
  long long tot = 0;
  for (int i = 1; i <= n; i++) tot += ssum[i];
  return tot - Dinic::max_flow(0, n + 1, n + 2);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) e[i].input();
  int st = 0, en = D;
  while (st < en - 1) {
    int mid1 = (st * 2 + en) / 3;
    int mid2 = (st + en * 2) / 3;
    long long ret1 = calc(mid1);
    if (ret1 == 0) {
      st = en = mid1;
      break;
    }
    long long ret2 = calc(mid2);
    if (ret2 == 0) {
      st = en = mid2;
      break;
    }
    if (ret1 > ret2) {
      st = mid1 + 1;
    } else {
      en = mid2;
    }
  }
  int ans = 0;
  {
    int lo = 0, hi = st;
    while (lo < hi) {
      int mid = lo + hi >> 1;
      if (calc(mid) == 0)
        hi = mid;
      else
        lo = mid + 1;
    }
    ans -= lo;
  }
  {
    int lo = st, hi = D;
    while (lo < hi) {
      int mid = lo + hi + 1 >> 1;
      if (calc(mid) == 0)
        lo = mid;
      else
        hi = mid - 1;
    }
    ans += lo;
  }
  printf("%.10lf\n", ans * 1.0 / D);
  return 0;
}