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 {
int nxt[100010 << 1], to[100010 << 1], head[100010], cnt = 1;
long long w[100010 << 1];
int all;
int adde(int u, int v, long long w1) {
  nxt[++cnt] = head[u];
  to[cnt] = v;
  w[cnt] = w1;
  head[u] = cnt;
  return cnt;
}
int add(int u, int v, long long w) {
  int p = adde(u, v, w);
  adde(v, u, 0);
  return p;
}
int dep[100010], cur[100010];
queue<int> q;
bool bfs(int s, int t) {
  for (int i = 1; i <= all; i++) dep[i] = 0, cur[i] = head[i];
  dep[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = nxt[i])
      if (w[i] && !dep[to[i]]) dep[to[i]] = dep[u] + 1, q.push(to[i]);
  }
  return dep[t];
}
long long dfs(int u, int t, long long flow = 1000000000000000ll) {
  if (u == t || !flow) return flow;
  long long r = 0;
  for (int &i = cur[u]; i; i = nxt[i]) {
    int v = to[i];
    long long f;
    if (dep[v] == dep[u] + 1 && (f = dfs(v, t, min(flow, w[i]))))
      w[i] -= f, w[i ^ 1] += f, flow -= f, r += f;
  }
  return r;
}
long long work(int s = all - 1, int t = all) {
  int r = 0;
  while (bfs(s, t)) r += dfs(s, t);
  return r;
}
void reset() {
  for (int i = 2; i <= cnt; i += 2) w[i] += w[i ^ 1], w[i ^ 1] = 0;
}
}  // namespace dinic
using dinic::add;
int n, m, ids[100010], idu[100010], idt[100010], a[100010], b[100010],
    c[100010], d[100010];
const int M = 100000000;
int solve(int t) {
  dinic::reset();
  long long s = 0;
  for (int i = 1; i <= m; i++) {
    dinic::w[ids[i]] = 1ll * t * a[i] + 1ll * M * b[i];
    dinic::w[idu[i]] = 1ll * t * (c[i] - a[i]) + 1ll * M * (d[i] - b[i]);
    dinic::w[idt[i]] = 1ll * t * a[i] + 1ll * M * b[i];
    s += 1ll * t * a[i] + 1ll * M * b[i];
  }
  return s - dinic::work();
}
int main() {
  scanf("%d%d", &n, &m);
  int s = n + 1, t = n + 2;
  dinic::all = t;
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d%d%d%d%d", &u, &v, &a[i], &b[i], &c[i], &d[i]);
    ids[i] = add(s, v, 0);
    idu[i] = add(u, v, 0);
    idt[i] = add(u, t, 0);
  }
  int l = 0, r = M;
  while (l + 1 < r) {
    int mid = (l + r) >> 1;
    if (solve(mid - 1) > solve(mid))
      l = mid;
    else
      r = mid;
  }
  int L = l;
  r = M;
  while (l + 1 < r) {
    int mid = (l + r) >> 1;
    if (solve(mid - 1))
      r = mid;
    else
      l = mid;
  }
  printf("%.7f", 1.0 * (r - L) / M);
  return 0;
}