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 = 10005;
struct edge {
  int to, next;
  long long f;
} e[N];
int head[N], tot, S, T;
int dis[N], q[N];
void add(int x, int y, long long v) {
  e[++tot] = (edge){y, head[x], v};
  head[x] = tot;
  e[++tot] = (edge){x, head[y], 0};
  head[y] = tot;
}
bool bfs() {
  for (int i = (int)(1); i <= (int)(T); i++) dis[i] = -1;
  int t = 1;
  dis[q[1] = S] = 0;
  for (int h = (int)(1); h <= (int)(t); h++)
    for (int i = head[q[h]]; i; i = e[i].next)
      if (dis[e[i].to] == -1 && e[i].f) {
        dis[e[i].to] = dis[q[h]] + 1;
        if (e[i].to == T) return 1;
        q[++t] = e[i].to;
      }
  return 0;
}
long long dfs(int x, long long flow) {
  if (x == T) return flow;
  long long k, rest = flow;
  for (int i = head[x]; i && rest; i = e[i].next)
    if (dis[e[i].to] == dis[x] + 1 && e[i].f) {
      k = dfs(e[i].to, min(rest, e[i].f));
      e[i].f -= k;
      e[i ^ 1].f += k;
      rest -= k;
    }
  if (rest) dis[x] = -1;
  return flow - rest;
}
int x[N], y[N], n, m;
int a[N], b[N], c[N], d[N];
long long deg[N], LIM = 100000000;
long long F(long long v) {
  for (int i = (int)(1); i <= (int)(n + 2); i++) head[i] = deg[i] = 0;
  S = n + 1;
  T = n + 2;
  tot = 1;
  for (int i = (int)(1); i <= (int)(m); i++) {
    long long L = a[i] * v + b[i] * LIM;
    long long R = c[i] * v + d[i] * LIM;
    add(x[i], y[i], R - L);
    deg[y[i]] += L;
    deg[x[i]] -= L;
  }
  long long ans = 0;
  for (int i = (int)(1); i <= (int)(n); i++)
    if (deg[i] > 0)
      add(S, i, deg[i]), ans += deg[i];
    else
      add(i, T, -deg[i]);
  for (; bfs(); ans -= dfs(S, 1ll << 60))
    ;
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (int)(1); i <= (int)(m); i++)
    scanf("%d%d%d%d%d%d", &x[i], &y[i], &a[i], &b[i], &c[i], &d[i]);
  int l = 0, r = LIM;
  for (; r - l >= 5;) {
    int 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> mn(8e18, 8e18);
  for (int i = (int)(l); i <= (int)(r); i++)
    mn = min(mn, pair<long long, long long>(F(i), i));
  if (mn.first) return puts("0"), 0;
  l = mn.second + 1;
  r = LIM;
  int ansr = mn.second;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (!F(mid))
      ansr = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  l = 0;
  r = mn.second - 1;
  int ansl = mn.second;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (!F(mid))
      ansl = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%.10lf\n", 1.0 * (ansr - ansl) / LIM);
}