Problem: In a forest, there lived a spider named Tim. Tim was so smart that he created a huge, well-structured web. Surprisingly, his web forms a set of equilateral and concentric N-sided polygons whose edge lengths form an arithmetic sequence.

<image>

Figure 1: An example web of Tim

Corresponding vertices of the N-sided polygons lie on a straight line, each apart from neighboring ver- tices by distance 1. Neighboring vertices are connected by a thread (shown in the figure as solid lines), on which Tim can walk (you may regard Tim as a point). Radial axes are numbered from 1 to N in a rotational order, so you can denote by (r, i) the vertex on axis i and apart from the center of the web by distance r. You may consider the web as infinitely large, i.e. consisting of infinite number of N-sided polygons, since the web is so gigantic.

Tim’s web is thus marvelous, but currently has one problem: due to rainstorms, some of the threads are damaged and Tim can’t walk on those parts.

Now, a bug has been caught on the web. Thanks to the web having so organized a structure, Tim accu- rately figures out where the bug is, and heads out for that position. You, as a biologist, are interested in whether Tim is smart enough to move through the shortest possible route. To judge that, however, you need to know the length of the shortest route yourself, and thereby decided to write a program which calculates that length.



Input

The input consists of multiple test cases. Each test case begins with a line containing two integers N (3 ≤ N ≤ 100) and X (0 ≤ X ≤ 100), where N is as described above and X denotes the number of damaged threads. Next line contains four integers rS, iS, rT, and iT, meaning that Tim is starting at (rS, iS) and the bug is at (rT, iT). This line is followed by X lines, each containing four integers rA, iA, rB, and iB, meaning that a thread connecting (rA, iA) and (rB, iB) is damaged. Here (rA, iA) and (rB, iB) will be always neighboring to each other. Also, for all vertices (r, i) given above, you may assume 1 ≤ r ≤ 107 and 1 ≤ i ≤ N.

There will be at most 200 test cases. You may also assume that Tim is always able to reach where the bug is.

The input is terminated by a line containing two zeros.

Output

For each test case, print the length of the shortest route in a line. You may print any number of digits after the decimal point, but the error must not be greater than 0.01.

Example

Input

5 1
2 1 3 2
2 1 2 2
0 0


Output

4.18

Solution (in CPP):

Solution:
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
typedef pair<int, int> P;
typedef pair<P, P> S;
typedef pair<double, P> state;

int main(){
  int N, X;
  while(cin>>N>>X && N){
    set<int> r_set;
    r_set.insert(1); r_set.insert(2);
    set<S> damage;
    int sr, sp, gr, gp;
    cin>>sr>>sp>>gr>>gp;
    sp--; gp--;
    r_set.insert(sr);
    r_set.insert(gr);
    r_set.insert(sr + 1);
    r_set.insert(gr + 1);
    if(sr != 1) r_set.insert(sr);
    if(gr != 1) r_set.insert(gr);
    REP(i, X){
      int r1, p1, r2, p2;
      cin>>r1>>p1>>r2>>p2;
      p1--; p2--;
      damage.insert(S(P(r1, p1), P(r2, p2)));
      damage.insert(S(P(r2, p2), P(r1, p1)));
      r_set.insert(r1);
      r_set.insert(r2);
      r_set.insert(r1 + 1);
      r_set.insert(r2 + 1);
      if(r1 >= 2) r_set.insert(r1 - 1);
      else r_set.insert(2);
      if(r2 >= 2) r_set.insert(r2 - 1);
      else r_set.insert(2);
    }
    vector<int> rs(r_set.begin(), r_set.end());
    int R = rs.size();
    //double dist[1000][100] = {};
    //REP(i, R)REP(j, N) dist[i][j] = 1e16;
    bool dist[1000][100] = {};
    int s_ridx = lower_bound(rs.begin(), rs.end(), sr) - rs.begin();
    priority_queue<state, vector<state>, greater<state> > que;
    que.push(state(0, P(s_ridx, sp)));
    while(!que.empty()){
      state s = que.top(); que.pop();
      int r_idx = s.second.first;
      int p = s.second.second;
      double d = s.first;
      //printf("(rs[%d]=%d, %d) = %lf\n", r_idx, rs[r_idx], p, d);
      if(rs[r_idx] == gr && p == gp){
        printf("%.2lf\n", d);
        break;
      }
      //if(dist[r_idx][p] < d) continue;
      if(dist[r_idx][p]) continue; dist[r_idx][p] = true;
      REP(r, 4){
        if(r % 2){
          int nr_idx = r_idx + r - 2;
          double nd = d + abs(rs[nr_idx] - rs[r_idx]);
          /*
          if(nr_idx >= 0 && nr_idx < R && dist[nr_idx][p] > nd && !damage.count(S(P(rs[r_idx], p), P(rs[nr_idx], p)))){
          */
          if(nr_idx >= 0 && nr_idx < R && !dist[nr_idx][p] && !damage.count(S(P(rs[r_idx], p), P(rs[nr_idx], p)))){
            //dist[r_idx][np] = nd;
            que.push(state(nd, P(nr_idx, p)));
          }
        }else{
          int np = (p + r - 1 + N) % N;
          double nd = (double)d + 2.0 * rs[r_idx] * sin(M_PI/N);
          /*
          if(dist[r_idx][np] > nd && !damage.count(S(P(rs[r_idx], p), P(rs[r_idx], np)))){
          */
          if(!dist[r_idx][np] && !damage.count(S(P(rs[r_idx], p), P(rs[r_idx], np)))){
            //dist[r_idx][np] = nd;
            que.push(state(nd, P(r_idx, np)));
          }
        }
      }
    }
  }

  return 0;
}