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 maxn = 1005;
const int maxm = 2005;
const long double eps = 1e-9;
int n, m;
int u[maxm], v[maxm], a[maxm], b[maxm], c[maxm], d[maxm];
namespace Flow {
const int maxv = maxn;
const int maxe = maxm * 3;
int S, T, V, tot;
int head[maxv], nxt[maxe << 1], to[maxe << 1];
long double cap[maxe << 1];
int lvl[maxv], que[maxv], cur[maxv];
void init() {
  tot = 0;
  memset(head, -1, sizeof(head));
}
void addedge(int u, int v, double c) {
  nxt[tot] = head[u];
  to[tot] = v;
  cap[tot] = c;
  head[u] = tot++;
  nxt[tot] = head[v];
  to[tot] = u;
  cap[tot] = 0;
  head[v] = tot++;
}
bool bfs() {
  for (int i = 0; i < V; i++) lvl[i] = -1;
  lvl[S] = 0;
  int ql = 0, qr = 0;
  que[qr++] = S;
  while (ql < qr) {
    int x = que[ql++];
    for (int i = head[x]; ~i; i = nxt[i])
      if (cap[i] > eps && lvl[to[i]] < 0) {
        lvl[to[i]] = lvl[x] + 1;
        que[qr++] = to[i];
      }
  }
  return lvl[T] >= 0;
}
long double dfs(int x, long double f) {
  if (x == T) return f;
  for (int &i = cur[x]; ~i; i = nxt[i])
    if (cap[i] > eps && lvl[to[i]] == lvl[x] + 1) {
      long double d = dfs(to[i], min(cap[i], f));
      if (d > eps) {
        cap[i] -= d;
        cap[i ^ 1] += d;
        return d;
      }
    }
  return 0;
}
long double work() {
  long double res = 0;
  while (bfs()) {
    for (int i = 0; i < V; i++) cur[i] = head[i];
    long double f;
    while ((f = dfs(S, 1e9)) > eps) res += f;
  }
  return res;
}
}  // namespace Flow
long double calc(long double t) {
  Flow::init();
  Flow::S = 0;
  Flow::T = n + 1;
  Flow::V = Flow::T + 2;
  long double tot = 0;
  for (int i = 1; i <= m; i++) {
    long double l = a[i] * t + b[i], r = c[i] * t + d[i];
    Flow::addedge(u[i], v[i], r - l);
    Flow::addedge(Flow::S, v[i], l);
    Flow::addedge(u[i], Flow::T, l);
    tot += l;
  }
  return Flow::work() - tot;
}
long double findP(long double l, long double r) {
  while (r - l > 1e-8) {
    long double midl = l + (r - l) / 3, midr = r - (r - l) / 3;
    long double vall = calc(midl), valr = calc(midr);
    if (vall < valr)
      l = midl;
    else
      r = midr;
  }
  return l;
}
long double findL(long double l, long double r) {
  while (r - l > 1e-8) {
    long double mid = (l + r) / 2;
    if (calc(mid) > -eps)
      r = mid;
    else
      l = mid;
  }
  return r;
}
long double findR(long double l, long double r) {
  while (r - l > 1e-8) {
    long double mid = (l + r) / 2;
    if (calc(mid) > -eps)
      l = mid;
    else
      r = mid;
  }
  return l;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++)
    scanf("%d%d%d%d%d%d", &u[i], &v[i], &a[i], &b[i], &c[i], &d[i]);
  long double p = findP(0, 1);
  printf("%.10lf\n", double(findR(p, 1) - findL(0, p)));
  return 0;
}