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 long long M = (long long)1e9;
struct edge {
  int r, nxt;
  long long w;
} e[10010 << 1];
long long deg[10010], a[10010], b[10010], c[10010], d[10010];
int fr[10010], to[10010], n, m;
int q[10010], l, r, cur[10010], dep[10010], head[10010], esz, S, T;
void addedge(int u, int v, long long w) {
  e[++esz].r = v;
  e[esz].nxt = head[u];
  head[u] = esz;
  e[esz].w = w;
  e[++esz].r = u;
  e[esz].nxt = head[v];
  head[v] = esz;
  e[esz].w = 0;
}
bool bfs() {
  for (int i = S; i <= T; ++i) cur[i] = head[i], dep[i] = 0;
  l = r = 0, q[r++] = S, dep[S] = 1;
  while (l < r) {
    int u = q[l++];
    for (int t = head[u]; t; t = e[t].nxt)
      if (e[t].w && !dep[e[t].r]) dep[e[t].r] = dep[u] + 1, q[r++] = e[t].r;
  }
  return dep[T] != 0;
}
long long find(int u, long long flow) {
  if (u == T) return flow;
  long long used = 0, a = 0;
  for (int& t = cur[u]; t; t = e[t].nxt)
    if (e[t].w && dep[e[t].r] == dep[u] + 1) {
      a = find(e[t].r, min(flow - used, e[t].w));
      used += a, e[t].w -= a, e[t ^ 1].w += a;
      if (flow == used) return used;
    }
  return used;
}
long long dinic() {
  long long ans = 0, a;
  while (bfs()) ans += find(S, 1ll << 60);
  return ans;
}
long long sol(long long t) {
  long long sum = 0;
  esz = 1, S = 0, T = n + 1;
  for (int i = S; i <= T; ++i) head[i] = deg[i] = 0;
  for (int i = 1; i <= m; ++i) {
    long long l = a[i] * t + b[i], r = c[i] * t + d[i];
    deg[to[i]] += l;
    deg[fr[i]] -= l;
    addedge(fr[i], to[i], r - l);
  }
  for (int i = 1; i <= n; ++i)
    if (deg[i] > 0)
      sum += deg[i], addedge(S, i, deg[i]);
    else
      addedge(i, T, -deg[i]);
  return sum - dinic();
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%lld%lld%lld%lld", &fr[i], &to[i], &a[i], &b[i], &c[i], &d[i]);
    b[i] *= M, d[i] *= M;
  }
  long long l = 0, r = M;
  for (int i = 0; r - l > 3; ++i) {
    long long mid1 = (l + l + r) / 3, mid2 = (l + r + r) / 3;
    long long f1 = sol(mid1), f2 = sol(mid2);
    if (f1 > f2)
      l = mid1;
    else
      r = mid2;
  }
  long long l1 = 0, r1 = l;
  for (int i = 0; l1 < r1; ++i) {
    long long mid = (l1 + r1) / 2;
    if (sol(mid) == 0)
      r1 = mid;
    else
      l1 = mid + 1;
  }
  long long l2 = l, r2 = M;
  for (int i = 0; l2 < r2; ++i) {
    long long mid = (l2 + r2) / 2;
    if (sol(mid) == 0)
      l2 = mid + 1;
    else
      r2 = mid;
  }
  printf("%.10lf", (double)(l2 - l1) / (double)M);
}