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;
template <typename T>
void UMAX(T &a, T b) {
  a = (a > b ? a : b);
}
template <typename T>
void UMIN(T &a, T b) {
  a = (a < b ? a : b);
}
long long readint() {
  char c = getchar();
  long long ret = 0ll;
  bool neg = 0;
  while (!(c >= '0' && c <= '9')) {
    if (c == '-') neg = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    ret = ret * 10ll + (long long)(c - '0');
    c = getchar();
  }
  return neg ? -ret : ret;
}
void putint(long long v) {
  if (v < 0) {
    putchar('-');
    v = -v;
  }
  if (!v) {
    putchar('0');
    return;
  }
  if (v >= 10ll) putint(v / 10ll);
  putchar('0' + (v % 10ll));
}
const int S = 1002, T = 1003, inf = 50000000;
namespace flows {
struct edge {
  int v, r, id;
  long double f;
  edge(int V, int R, long double F, int _id) {
    v = V;
    r = R;
    f = F;
    id = _id;
  }
};
vector<edge> adj[1005];
int cur[1005], dis[1005];
void init() {
  int i;
  for (i = 0; i < 1005; ++i) {
    adj[i].clear();
  }
}
void addedge(int u, int v, long double f, int id, bool bi = 0) {
  adj[u].push_back(edge(v, (int)adj[v].size(), f, id));
  adj[v].push_back(edge(u, (int)adj[u].size() - 1, bi ? f : 0, -1));
}
void bfs() {
  queue<int> Q;
  Q.push(S);
  dis[S] = 0;
  while (!Q.empty()) {
    int i, cv = Q.front();
    Q.pop();
    for (i = 0; i < (int)adj[cv].size(); ++i) {
      if (adj[cv][i].f > 1e-8l && dis[adj[cv][i].v] == -1) {
        dis[adj[cv][i].v] = dis[cv] + 1;
        Q.push(adj[cv][i].v);
      }
    }
  }
}
long double dfs(int ver, long double cap) {
  if (ver == T) return cap;
  for (int &i = cur[ver]; i < (int)adj[ver].size(); ++i) {
    edge &E = adj[ver][i];
    if (E.f > 1e-8l && dis[E.v] > dis[ver]) {
      long double ret = dfs(E.v, min(cap, E.f));
      if (ret > 1e-8l) {
        E.f -= ret;
        adj[E.v][E.r].f += ret;
        return ret;
      }
    }
  }
  return 0;
}
long double maxflow() {
  long double ret = 0, dlt;
  while (1) {
    memset(dis, -1, sizeof(dis));
    memset(cur, 0, sizeof(cur));
    bfs();
    if (dis[T] == -1) return ret;
    dlt = 1;
    while (dlt > 1e-8l) {
      dlt = dfs(S, 1e9l);
      ret += dlt;
    }
  }
}
}  // namespace flows
int n, m;
vector<int> U, V, A, B, C, D;
long double calc(long double t) {
  flows::init();
  int i, j, k;
  long double suml = 0;
  for (i = 0; i < m; ++i) {
    int u = U[i], v = V[i], a = A[i], b = B[i], c = C[i], d = D[i];
    long double l = a * t + b, r = c * t + d;
    suml += l;
    flows::addedge(S, v, l, -1);
    flows::addedge(u, T, l, -1);
    flows::addedge(u, v, r - l, -1);
  }
  return flows::maxflow() - suml;
}
long double getpeak() {
  long double l = 0, r = 1;
  while (r - l > 1e-7l) {
    long double dif = (r - l) / 3;
    long double mid1 = l + dif, mid2 = l + dif + dif;
    if (calc(mid1) < calc(mid2))
      l = mid1;
    else
      r = mid2;
  }
  return l;
}
long double getR(long double peak) {
  long double l = peak, r = 1, mid;
  while (r - l > 1e-7l) {
    mid = (l + r) / 2;
    if (calc(mid) > -1e-8l)
      l = mid;
    else
      r = mid;
  }
  return l;
}
long double getL(long double peak) {
  long double l = 0, r = peak, mid;
  while (r - l > 1e-7l) {
    mid = (l + r) / 2;
    if (calc(mid) > -1e-8l)
      r = mid;
    else
      l = mid;
  }
  return l;
}
int main() {
  int i, j, k;
  n = readint();
  m = readint();
  for (i = 0; i < m; ++i) {
    int u = readint() - 1, v = readint() - 1, a = readint(), b = readint(),
        c = readint(), d = readint();
    U.push_back(u);
    V.push_back(v);
    A.push_back(a);
    B.push_back(b);
    C.push_back(c);
    D.push_back(d);
  }
  long double p = getpeak();
  printf("%.10f\n", (double)(getR(p) - getL(p)));
  return 0;
}