#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define int long long
#define st first
#define nd second
#define rd third
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define RE(i, n) FOR(i, 1, n)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define cerr if(0)cout
#endif
#define next ____next
#define prev ____prev
#define left ____left
#define hash ____hash
typedef long long ll;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<pair<int, int> > VPII;
typedef vector<pair<ll, ll> > VPLL;

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
template<class A, class B, class C> struct Triple { A first; B second; C third;
  bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
template<class T> void ResizeVec(T&, vector<int>) {}
template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  for (T& v : vec) { ResizeVec(v, sz); }
}
typedef Triple<int, int, int> TIII;
template<class A, class B, class C>
ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }

const LD kEps = 1e-9;
const LD kPi = 2 * acos(0);
LD Sq(LD x) {
  return x * x;
}
struct Point {
  LD x, y;
  Point() {}
  Point(LD a, LD b) : x(a), y(b) {}
  Point(const Point& a) : x(a.x), y(a.y) {}
  void operator=(const Point& a) { x = a.x; y = a.y; }
  Point operator+(const Point& a) const { Point p(x + a.x, y + a.y); return p; }
  Point operator-(const Point& a) const { Point p(x - a.x, y - a.y); return p; }
  Point operator*(LD a) const { Point p(x * a, y * a); return p; }
  Point operator/(LD a) const { assert(abs(a) > kEps); Point p(x / a, y / a); return p; }
  Point& operator+=(const Point& a) { x += a.x; y += a.y; return *this; }
  Point& operator-=(const Point& a) { x -= a.x; y -= a.y; return *this; }
  Point& operator*=(LD a) { x *= a; y *= a; return *this;}
  Point& operator/=(LD a) { assert(abs(a) > kEps); x /= a; y /= a; return *this; }
  
  bool IsZero() const {
    return abs(x) < kEps && abs(y) < kEps;
  }
  bool operator==(const Point& a) const {
    return (*this - a).IsZero();
  }
  LD CrossProd(const Point& a) const {
    return x * a.y - y * a.x;
  }
  LD CrossProd(Point a, Point b) const {
    a -= *this;
    b -= *this;
    return a.CrossProd(b);
  }
  LD DotProd(const Point& a) const {
    return x * a.x + y * a.y;
  }
  LD Norm() const {
    return sqrt(Sq(x) + Sq(y));
  }
  void NormalizeSelf() {
    *this /= Norm();
  }
  Point Normalize() {
    Point res(*this);
    res.NormalizeSelf();
    return res;
  }
  LD Dist(const Point& a) const {
    return (*this - a).Norm();
  }
  LD Angle() const {
    return atan2(y, x);
  }
  void RotateSelf(LD angle) {
    LD c = cos(angle);
    LD s = sin(angle);
    LD nx = x * c - y * s;
    LD ny = y * c + x * s;
    y = ny;
    x = nx;
  }
  Point Rotate(LD angle) const {
    Point res(*this);
    res.RotateSelf(angle);
    return res;
  }
  static bool LexCmp(const Point& a, const Point& b) {
    if (abs(a.x - b.x) > kEps) {
      return a.x < b.x;
    }
    return a.y < b.y;
  }
  LD SqNorm() {
    return x * x + y * y;
  }
  friend ostream& operator<<(ostream& out, Point m);
};

ostream& operator<<(ostream& out, Point p) {
  out << "(" << p.x << ", " << p.y << ")";
  return out;
}

struct Circle {
  Point center;
  LD r;
  Circle(LD x, LD y, LD rad) {
    center = Point(x, y);
    r = rad;
  }
  Circle(const Point& a, LD rad) : center(a), r(rad) {}
  LD Area() const {
    return kPi * Sq(r);
  }
  LD Perimeter() const {
    return 2 * kPi * r;
  }
  LD Diameter() const {
    return 2 * r;
  }
  Point RotateRightMost(LD ang) const {
    return center + Point{r * cos(ang), r * sin(ang)};
  }
  bool operator==(const Circle& c) const {
    return center == c.center && abs(r - c.r) < kEps;
  }
};

struct Line {
  Point p[2];
  bool is_seg;
  Line(Point a, Point b, bool is_seg_ = false) {
    p[0] = a;
    p[1] = b;
    is_seg = is_seg_;
  }
  Line() {
  }
  Point& operator[](int a) {
    return p[a];
  }
  Point NormalVector() {
    Point perp = p[1] - p[0];
    perp.RotateSelf(kPi / 2);
    perp.NormalizeSelf();
    return perp;
  }
  
  // (A, B, C) such that A^2 + B^2 = 1, (A, B) > (0, 0)
  vector<LD> LineEqNormLD() { // seems ok
    LD A = p[1].y - p[0].y;
    LD B = p[0].x - p[1].x;
    LD C = -(A * p[0].x + B * p[0].y);
    assert(abs(A * p[1].x + B * p[1].y + C) < kEps);
    LD norm = sqrt(Sq(A) + Sq(B));
    vector<LD> res{A, B, C};
    for (auto& x : res) { x /= norm; }
    if (A < -kEps || (abs(A) < kEps && B < -kEps)) {
      for (auto& x : res) { x *= -1; }
    }
    return res;
  }
  
  // assumes that coordinates are integers!
  vector<int> LineEqNormInt() { // seems ok
    int A = round(p[1].y - p[0].y);
    int B = round(p[0].x - p[1].x);
    int C = -(A * p[0].x + B * p[0].y);
    int gcd = abs(__gcd(A, __gcd(B, C)));
    vector<int> res{A, B, C};
    for (auto& x : res) { x /= gcd; }
    if (A < 0 || (A == 0 && B < 0)) {
      for (auto& x : res) { x *= -1; }
    }
    return res;
  }
};

struct Utils {
  // 0, 1, 2 or 3 pts. In case of 3 pts it means they are equal
  static vector<Point> InterCircleCircle(Circle a, Circle b) {
    if (a.r + kEps < b.r) {
      swap(a, b);
    }
    if (a == b) {
      return vector<Point>{a.RotateRightMost(0), a.RotateRightMost(2 * kPi / 3),
          a.RotateRightMost(4 * kPi / 3)};
    }
    Point diff = b.center - a.center;
    LD dis = diff.Norm();
    LD ang = diff.Angle();
    LD longest = max(max(a.r, b.r), dis);
    LD per = a.r + b.r + dis;
    if (2 * longest > per + kEps) {
      return vector<Point>();
    }
    if (abs(2 * longest - per) < 2 * kEps) {
      return vector<Point>{a.RotateRightMost(ang)};
    }
    LD ang_dev = acos((Sq(a.r) + Sq(dis) - Sq(b.r)) / (2 * a.r * dis));
    return vector<Point>{a.RotateRightMost(ang - ang_dev), a.RotateRightMost(ang + ang_dev)};
  }
  
  static vector<Point> InterLineLine(Line& a, Line& b) { // working fine
    Point vec_a = a[1] - a[0];
    Point vec_b1 = b[1] - a[0];
    Point vec_b0 = b[0] - a[0]; 
    LD tr_area = vec_b1.CrossProd(vec_b0);
    LD quad_area = vec_b1.CrossProd(vec_a) + vec_a.CrossProd(vec_b0);
    if (abs(quad_area) < kEps) { // parallel or coinciding
      if (PtBelongToLine(b, a[0])) {
        return {a[0], a[1]};
      } else {
        return {};
      }
    }
    return {a[0] + vec_a * (tr_area / quad_area)};
  } 
  
  static Point ProjPointToLine(Point p, Line l) { ///Tested
    Point diff = l[1] - l[0];
    return l[0] + diff * (diff.DotProd(p - l[0]) / diff.DotProd(diff));
  }
  
  static Point ReflectPtWRTLine(Point p, Line l) {
    Point proj = ProjPointToLine(p, l);
    return proj * 2 - p;
  }
  
  static vector<Point> InterCircleLine(Circle c, Line l) { /// Tested here: http://c...content-available-to-author-only...s.com/gym/100554/submission/10197624
    Point proj = ProjPointToLine(c.center, l);
    LD dis_proj = c.center.Dist(proj);
    if (dis_proj > c.r + kEps) { return vector<Point>(); }
    LD a = sqrt(max((LD)0, Sq(c.r) - Sq(dis_proj)));
    Point dir = l[1] - l[0];
    LD dir_norm = dir.Norm();
    vector<Point> cands{proj + dir * (a / dir_norm), proj - dir * (a / dir_norm)};
    if (cands[0].Dist(cands[1]) < kEps) { return vector<Point>{proj}; }
    return cands;
  }
  
  static bool PtBelongToLine(Line l, Point p) {
    return abs(l[0].CrossProd(l[1], p)) < kEps;
  }
  
  static bool PtBelongToSeg(Line l, Point p) { // seems ok
    return abs(p.Dist(l[0]) + p.Dist(l[1]) - l[0].Dist(l[1])) < kEps;
  }
  
  static vector<Point> InterCircleSeg(Circle c, Line l) { //seems ok
    vector<Point> from_line = InterCircleLine(c, l);
    vector<Point> res;
    for (auto p : from_line) {
      if (PtBelongToSeg(l, p)) { res.PB(p); }
    }
    return res;
  }
  
  static vector<Point> TangencyPtsToCircle(Circle c, Point p) { // seems ok
    LD d = c.center.Dist(p);
    if (d < c.r - kEps) { return {}; }
    if (d < c.r + kEps) { return {p}; }
    LD from_cent = (p - c.center).Angle();
    LD ang_dev = acos(c.r / d);
    return {c.RotateRightMost(from_cent - ang_dev), c.RotateRightMost(from_cent + ang_dev)};
  }
  
  // outer and inner tangents tested only locally (however I believe that rigorously)
  static vector<Line> OuterTangents(Circle c1, Circle c2) {
    if (c1 == c2) { return {}; } // is it surely best choice?
    if (c1.r < c2.r) { swap(c1, c2); }
    if (c2.r + c1.center.Dist(c2.center) < c1.r - kEps) { return {}; }
    if (abs(c1.r - c2.r) < kEps) {
      Point diff = c2.center - c1.center;
      Point R = diff.Rotate(kPi / 2) * (c1.r / diff.Norm()); 
      return {{c1.center + R, c2.center + R}, {c1.center - R, c2.center - R}};
    }
    Point I = c1.center + (c2.center - c1.center) * (c1.r / (c1.r - c2.r)); 
    if (c2.r + c1.center.Dist(c2.center) < c1.r + kEps) {
      return {{I, I + (c2.center - c1.center).Rotate(kPi / 2)}};
    }
    vector<Point> to1 = TangencyPtsToCircle(c1, I);
    vector<Point> to2 = TangencyPtsToCircle(c2, I);
    vector<Line> res{{to1[0], to2[0]}, {to1[1], to2[1]}};
    assert(Utils::PtBelongToLine(res[0], I));
    assert(Utils::PtBelongToLine(res[1], I));
    return res;
  }
    
  // unfortunately big part of code is same as in previous function
  // can be joined when putting appropriate signs in few places
  // however those ifs differ a bit hence it may not be good idea
  // to necessarily join them
  static vector<Line> InnerTangents(Circle c1, Circle c2) {
    if (c1 == c2) { return {}; } // this time surely best choice
    if (c1.r < c2.r) { swap(c1, c2); }
    LD d = c1.center.Dist(c2.center);
    if (d < c1.r + c2.r - kEps) { return {}; }
    Point I = c1.center + (c2.center - c1.center) * (c1.r / (c1.r + c2.r));
    if (d < c1.r + c2.r + kEps) {
      return {{I, I + (c2.center - c1.center).Rotate(kPi / 2)}};
    }
    vector<Point> to1 = TangencyPtsToCircle(c1, I);
    vector<Point> to2 = TangencyPtsToCircle(c2, I);
    vector<Line> res{{to1[0], to2[0]}, {to1[1], to2[1]}};
    assert(Utils::PtBelongToLine(res[0], I));
    assert(Utils::PtBelongToLine(res[1], I));
    return res;
  }
  
  static bool AreParallel(Line l1, Line l2) { // seems ok
    return abs(l1[0].CrossProd(l2[0], l1[1]) - l1[0].CrossProd(l2[1], l1[1])) < kEps;
  }
  
  // returns a vector of points such that their convex hull is intersection of those segments
  // SZ(res) == 0 => empty intersection, SZ(res) == 1 => intersection is a point, SZ(res) == 2 => intersection is a segment
  static vector<Point> InterSegs(Line l1, Line l2) { // seems ok
    if (!Point::LexCmp(l1[0], l1[1])) { swap(l1[0], l1[1]); }
    if (!Point::LexCmp(l2[0], l2[1])) { swap(l2[0], l2[1]); }
    if (AreParallel(l1, l2)) {
      if (!PtBelongToLine(l1, l2[0])) { return vector<Point>(); }
      vector<Point> ends(2);
      for (int tr = 0; tr < 2; tr++) {
        if (Point::LexCmp(l1[tr], l2[tr]) ^ tr) {
          ends[tr] = l2[tr];
        } else {
          ends[tr] = l1[tr];
        }
      }
      if ((ends[1] - ends[0]).IsZero()) {
        ends.pop_back();
      }
      if (SZ(ends) == 2 && Point::LexCmp(ends[1], ends[0])) { return vector<Point>(); }
      return ends;
    } else {
      vector<Point> p = InterLineLine(l1, l2);
      if (PtBelongToSeg(l1, p[0]) && PtBelongToSeg(l2, p[0])) { return p; }
      return vector<Point>();
    }
  }
  
  static LD Angle(Point P, Point Q, Point R) { // angle PQR
    LD ang2 = (P - Q).Angle();
    LD ang1 = (R - Q).Angle();
    LD ans = ang1 - ang2;
    if (ans < kEps) {
      ans += 2 * kPi;
    }
    return ans;
  }
  
  // tested here: http://c...content-available-to-author-only...s.com/contest/600/submission/14961583
  // DON'T change anything as this will lead to precision errors
  // don't know why, but this is the only version which works precisely even for very mean cases
  static LD DiskInterArea(Circle c1, Circle c2) { // tested here: http://o...content-available-to-author-only...s.info/~ejudge/team.cgi?contest_id=006254 problem I
    if (c1.r < c2.r) {
      swap(c1, c2);
    }
    LD d = c1.center.Dist(c2.center);
    if (c1.r + c2.r < d + kEps) {
      return 0;
    }
    if (c1.r - c2.r > d - kEps) {
      return kPi * Sq(c2.r);
    }
    LD alfa = acos((Sq(d) + Sq(c1.r) - Sq(c2.r)) / (2 * d * c1.r));
    LD beta = acos((Sq(d) + Sq(c2.r) - Sq(c1.r)) / (2 * d * c2.r));
    return alfa * Sq(c1.r) + beta * Sq(c2.r) - sin(2 * alfa) * Sq(c1.r) / 2 - sin(2 * beta) * Sq(c2.r) / 2;
  }
  
  static Line RadAxis(Circle c1, Circle c2) {
    LD d = c1.center.Dist(c2.center);
    LD a = (Sq(c1.r) - Sq(c2.r) + Sq(d)) / (2 * d);
    Point Q = c1.center + (c2.center - c1.center) * (a / d);
    Point R = Q + (c2.center - c1.center).Rotate(kPi / 2);
    return Line(Q, R);
  }
};

struct Polygon {
  vector<Point> pts;
  Polygon(vector<Point> pts_) : pts(pts_) {}
  Polygon() : Polygon(vector<Point>()) {}
  void Add(Point p) {
    pts.push_back(p);
  }
  // positive for counterclockwise
  double Area() {
    double area = 0;
    for (int i = 0; i < SZ(pts); i++) {
      area += pts[i].CrossProd(pts[(i + 1) % SZ(pts)]);
    }
    area /= 2;
    return area;
  }
  void OrientCounterclockwise() {
    if (Area() < 0) {
      reverse(pts.begin(), pts.end());
    }
  }
  int next(int a) {
    if (a + 1 < SZ(pts)) {
      return a + 1;
    }
    return 0;
  }
  pair<int, int> FurthestPair() { // tested here: http://c...content-available-to-author-only...s.com/contest/333/submission/11058065
    MakeConvexHull();
    OrientCounterclockwise();
    int furth = 1;
    pair<int, int> best_pair = make_pair(0, 0);
    double best_dis = 0;
    for (int i = 0; i < SZ(pts); i++) {
      Point side = pts[next(i)] - pts[i];
      while (side.CrossProd(pts[furth] - pts[i]) < side.CrossProd(pts[next(furth)] - pts[i])) {
        furth = next(furth);
      }
      vector<int> vec{i, next(i)};
      for (auto ind : vec) {
        if (pts[ind].Dist(pts[furth]) > best_dis) {
          best_pair = make_pair(ind, furth);
          best_dis = pts[ind].Dist(pts[furth]);
        }
      }
      cerr<<"Furthest from: "<<pts[i]<<"-"<<pts[next(i)]<<" is "<<pts[furth]<<endl;
    }
    return best_pair;
  }
  // for square 34 
  //            12 holds one_way_hull = {{1,3,4},{1,2,4}}
  // resulting polygon is counterclockwise {1, 2, 4, 3}
  vector<vector<Point>> MakeConvexHull() { // tested everywhere http://c...content-available-to-author-only...s.com/contest/333/submission/11058065
    vector<vector<Point>> one_way_hull(2);
    sort(pts.begin(), pts.end(), Point::LexCmp);
    for (int dir = -1; dir <= 1; dir += 2) {
      int hull_num = (dir + 1) / 2;
      auto& H = one_way_hull[hull_num];
      one_way_hull[hull_num].push_back(pts[0]);
      if (SZ(pts) > 1) {
        H.push_back(pts[1]);
      }
      for (int i = 2; i < SZ(pts); i++) {
        while (SZ(H) >= 2 &&
            dir * (pts[i] - H[SZ(H) - 2]).CrossProd(H.back() - H[SZ(H) - 2]) > -kEps) {
          H.pop_back();
        }
        H.push_back(pts[i]);
      }
      if (SZ(H) > 1 && (H[0] - H.back()).IsZero()) { H.pop_back(); }
    }
    pts.clear();
    for (auto p : one_way_hull[1]) {
      pts.push_back(p);
    }
    for (int i = SZ(one_way_hull[0]) - 2; i >= 1; i--) {
      pts.push_back(one_way_hull[0][i]);
    }
    return one_way_hull;
  }
  
  // without sides
  vector<vector<bool>> InsideDiagonalsMatrix() { // tested here: http://c...content-available-to-author-only...s.com/contest/438/submission/11063385
    int n = pts.size();
    vector<vector<bool>> res(n, vector<bool>(n));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        Line diag(pts[i], pts[j]);
        if (i == j || abs(i - j) == 1 || abs(i - j) == n - 1) { continue; }
        res[i][j] = 1;
        for (int k = 0; k < n; k++) {
          int kk = next(k);
          Line side(pts[k], pts[kk]);
          if (k == i || k == j || kk == i || kk == j) { continue; }
          vector<Point> inter = Utils::InterSegs(diag, side);
          if (SZ(inter)) { res[i][j] = 0; }
        }
        int act = next(i);
        LD areas[2] = {0, 0};
        int passed_j = 0;
        while (act != i) {
          passed_j |= (act == j);
          areas[passed_j] += pts[i].CrossProd(pts[act], pts[next(act)]);
          act = next(act);
        }
        if (areas[0] * areas[1] < kEps) {
          res[i][j] = 0;
        }
      }
    }
    return res;
  }
  
  // P needs to be strictly outside polygon 
  // polygon needs to be STRICTLY convex and counterclockwise oriented (as MakeConvexHull does)
  // returns {L, R} so that PL, PR are tangents and PL is on left
  vector<Point> Tangents(Point p) { // tested here: https://i...content-available-to-author-only...s.com/problems/spin (1169964)
    vector<Point> res;
    REP (tr, 2) {
      auto GrThan = [&](int fir, int sec) { // fir on sec's left
        return p.CrossProd(pts[sec], pts[fir]) > kEps;
      };
      bool up = false;
      int cr = 0;
      if (SZ(pts) >= 2) { cr = p.CrossProd(pts[0], pts[1]); }
      if (abs(cr) < kEps && SZ(pts) >= 3) { cr = p.CrossProd(pts[0], pts[2]); }
      up = (cr > 0);
      VI bd{1, SZ(pts) - 1};
      int faj = 0;
      while (bd[0] + 6 <= bd[1]) { // better don't replace with smaller constants
        VI h(2);
        REP (hh, 2) { h[hh] = (bd[0] + bd[1] + bd[hh]) / 3; }
        if (!GrThan(h[up ^ tr], 0) ^ tr) { bd[up ^ tr] = h[up ^ tr]; }
        else {
          int gr = GrThan(h[0], h[1]);
          bd[gr ^ tr] = h[gr ^ tr];
        }
      }
      FOR (i, bd[0], bd[1]) {
        if (GrThan(i, faj) ^ tr) {
          faj = i;
        }
      }
      res.PB(pts[faj]);
    }
    return res;
  }
};

struct ConvexPolHalves { // tested here: https://i...content-available-to-author-only...s.com/problems/spin (1169964)
  vector<vector<Point>> chains; // initialized by MakeConvexHull
  bool BelongTo(Point p) { // including borders
    if (SZ(chains[0]) == 1) {
      return (chains[0][0] - p).IsZero();
    }
    if (p.x  + kEps < chains[0][0].x || p.x - kEps > chains[0].back().x) { return false; }
    REP (tr, 2) {
      int kl = 0, kp = SZ(chains[tr]) - 2, faj = 0;
      while (kl <= kp) {
        int aktc = (kl + kp) / 2;
        if (chains[tr][aktc].x < p.x + kEps) {
          kl = aktc + 1;
          faj = aktc;
        } else {
          kp = aktc - 1;
        }
      }
      Point fir = chains[tr][faj], sec = chains[tr][faj + 1];
      if (abs(fir.x - sec.x) < kEps) {
        if (tr == 0) { if (sec.y + kEps < p.y) { return false; } }
        else { if (fir.y - kEps > p.y) { return false; } }
      } else {
        LD cr = fir.CrossProd(sec, p);
        if (abs(cr) < kEps) { return true; }
        if ((cr > 0) ^ tr) { return false; }
      }
    }
    return true;
  }
};

// CLIP START
bool InUpper(Point a) {
  if (abs(a.y) > kEps) {
    return a.y > 0;
  }
  return a.x > 0;
}

bool angle_cmp(const Point a, const Point b) {
  bool u = InUpper(a);
  bool v = InUpper(b);
  return u!=v ? u : a.CrossProd(b)>0;
}

/**
  * @brief a+(b-a)*f \in c+lin(d-c)
  * @returns f
  */
LD cross(Point a, Point b, Point c, Point d) {
  return (d - c).CrossProd(a - c) / (d - c).CrossProd(a - b);
}

struct ClipLine { // valid side is on left
  ClipLine(Point A, Point B) : al(A), bl(B), a(A), b(B) {};
  Point al,bl; // original line points
  mutable Point a,b; // actual intersection points
  Point dir() const { return bl - al; }
  bool operator<(const ClipLine& l) const { return angle_cmp(dir(),l.dir()); }
  Point cross(const ClipLine& l) {
    return al + (bl - al) * ::cross(al, bl, l.al, l.bl);
  }
  bool left(Point p) {
    return (bl - al).CrossProd(p - al) > 0;
  }
};

struct Clip {
  Clip(LD r) : area(4*r*r) {
    Point a{-r,-r}, b{r,-r}, c{r,r}, d{-r,r};
    lines = {ClipLine(a,b), ClipLine(b,c), ClipLine(c,d), ClipLine(d,a)};
  }

  void insert(Line l) { insert(ClipLine(l[0], l[1])); }
  
  void insert(ClipLine l) {
    assert(abs(l.dir().SqNorm()) > kEps);
    find(l);
    while (size() && !l.left(it->a) && !l.left(it->b)) { erase(); }
    if (size()) {
      while (prev(), size() && !l.left(it->a) && !l.left(it->b)) { erase(); }
    }
    if (size() && (!l.left(it->a) || !l.left(it->b))) {
      l.a = l.cross(*it);
      area -= l.a.CrossProd(it->b)*.5; it->b = l.a; next();
      l.b = l.cross(*it);
      if ((l.a-l.b).SqNorm() < kEps) {
        l.b = l.a;
      }
      area -= it->a.CrossProd(l.b) * .5;
      it->a = l.b;
      if (!(l.a - l.b).IsZero()) {
        area += l.a.CrossProd(l.b)*.5;
        lines.insert(l);
      }
    }
    //assert(l.dir().SqNorm()>1e-13);
  }

  void find(const ClipLine &l) {
    it = lines.lower_bound(l);
    if (it == lines.end()) { it = lines.begin(); }
  }

  void recalculate() {
    area = 0; for (const ClipLine &l : lines) area += l.a.CrossProd(l.b);
    area *= .5;
  }

  int size() { return lines.size(); }
  void next() { if(++it==lines.end()) it = lines.begin(); }
  void prev() { if(it==lines.begin()) it = lines.end(); --it; }
  void erase() {
      assert(it!=lines.end());
      area -= it->a.CrossProd(it->b)*.5;
      it = lines.erase(it);
      if(it==lines.end()) it = lines.begin();
  }
  typename set<ClipLine>::iterator it;
  set<ClipLine> lines;
  LD area;
};
// CLIP ENDS

// CENTERS BEGIN
Point Bary(Point A, Point B, Point C, LD a, LD b, LD c) {
    return (A * a + B * b + C * c) / (a + b + c);
}

Point Centroid(Point A, Point B, Point C) {
    return Bary(A, B, C, 1, 1, 1);
}

Point Circumcenter(Point A, Point B, Point C) {
    LD a = (B - C).SqNorm(), b = (C - A).SqNorm(), c = (A - B).SqNorm();
    return Bary(A, B, C, a * (b + c - a), b * (c + a - b), c * (a + b - c));
}

Point Incenter(Point A, Point B, Point C) {
    return Bary(A, B, C, (B - C).Norm(), (A - C).Norm(), (A - B).Norm());
}

Point Orthocenter(Point A, Point B, Point C) {
    LD a = (B - C).SqNorm(), b = (C - A).SqNorm(), c = (A - B).SqNorm();
    return Bary(A, B, C, (a+b-c)*(c+a-b), (b+c-a)*(a+b-c), (c+a-b)*(b+c-a));
}

Point Excenter(Point A, Point B, Point C) { // opposite to A
    LD a = (B - C).Norm(), b = (A - C).Norm(), c = (A - B).Norm();
    return Bary(A, B, C, -a, b, c);
}


LD RandLD(LD a, LD b) {
  int R = 1 << 28;
  LD r = (rand() % R) * 1. / R;
  return a + (b - a) * r;
}

const LD R = 1.5;
const LD V = 0.5;
const LD S = 1;
const LD L = 0.6;
const int K = 10;
const int T = 100;
const int M = 20000;

LD RandMean() {
  LD sum = 0;
  REP (i, K) {
    sum += RandLD(-0.1, 0.1);
  }
  return sum / K;
}

const int N = 1005;
Point pt[N];

LD DisPtSeg(Point p, Line l) {
  Point proj = Utils::ProjPointToLine(p, l);
  if (Utils::PtBelongToSeg(l, proj)) {
    return p.Dist(proj);
  }
  return min(p.Dist(l[0]), p.Dist(l[1]));
}

int32_t main() {

  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(4);
  cerr << fixed << setprecision(4);
  cin.tie(0);
  //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  
  srand(22345);
  //srand(222);
  
//   LD sumrr = 0;
//   int tries = 1000;
//   REP (tr, tries) {
//     LD r = RandMean();
//     sumrr += r * r;
//     debug(r);
//   }
//   debug(sqrt(sumrr / tries));
  
  Point cur;
  LD dir;
  int nxt_get = 1;
//   VI last_closest[2];
#ifdef LOCAL
  int n;
  cin>>n;
  LD shortest = 1e9;
  LD smallest_angle = kPi;
  LD sum_len = 0;
  RE (i, n) {
    LD x, y;
    cin>>x>>y;
    pt[i] = {x, y};
    if (i >= 2) {
      mini(shortest, pt[i].Dist(pt[i - 1]));
      sum_len += pt[i].Dist(pt[i - 1]);
    }
    if (i >= 3) {
      Point dir1 = pt[i] - pt[i - 1];
      Point dir2 = pt[i - 2] - pt[i - 1];
      LD ang_diff = dir1.Angle() - dir2.Angle();
      while (ang_diff < 0) {
        ang_diff += 2 * kPi;
      }
      while (ang_diff > 2 * kPi - kEps) {
        ang_diff -= 2 * kPi;
      }
      if (ang_diff > kPi - kEps) {
        ang_diff = 2 * kPi - ang_diff;
      }
      mini(smallest_angle, ang_diff);
    }
  }
  debug(shortest, sum_len, smallest_angle);
//   return 0;
  cur = pt[1];
  dir = (pt[2] - pt[1]).Angle() + RandLD(-0.2, 0.2);
  int steps = 0;
#endif
  int nxt_to_pass = 2;
  LD prv1 = 0.95, prv2 = 0.95;
  LD sen1 = 0.95, sen2 = 0.95;
  function<void()> Get = [&]() {
    assert(nxt_get);
    nxt_get ^= 1;
    prv1 = sen1;
    prv2 = sen2;
#ifdef LOCAL
    if (nxt_to_pass == n + 1) {
      sen1 = -1;
      sen2 = -1;
      if (sen1 < -0.5) {
        debug(steps);
        exit(0);
      }
      return;
    }
    vector<LD> d{5, 5};
    vector<Point> wheel(2);
    bool is_any_inter = false;
    wheel[0] = cur + Point{cos(dir + kPi / 2), sin(dir + kPi / 2)} * R;
    wheel[1] = cur + Point{cos(dir - kPi / 2), sin(dir - kPi / 2)} * R;
    REP (tr, 2) {
      RE (i, n - 1) {
        mini(d[tr], DisPtSeg(wheel[tr], Line{pt[i], pt[i + 1]}));
      }
    }
    RE (i, n - 1) {
      if (!Utils::InterSegs(Line{wheel[0], wheel[1]}, Line{pt[i], pt[i + 1]}).empty()) {
        is_any_inter = true;
        break;
      }
    }
    if (!is_any_inter) {
      debug(nxt_to_pass);
      debug("!!!!!!!!!!!!!!!!!!!");
    }
//     assert(is_any_inter);
    if (d[0] > R + S + L || d[1] > R + S + L) {
      debug(nxt_to_pass);
      assert(false);
    }
    sen1 = 1 - max((LD)0, min(S, d[0] + L) - max(-S, d[0] - L)) / (2 * S);
    sen2 = 1 - max((LD)0, min(S, d[1] + L) - max(-S, d[1] - L)) / (2 * S);
    sen1 = min((LD)1, sen1 + RandMean());
    sen2 = min((LD)1, sen2 + RandMean());
#else
    cin>>sen1>>sen2;
#endif
    if (sen1 < -0.5) {
      exit(0);
    }
  };
  
  function<void(LD, LD)> Go = [&](LD cl, LD cr) {
    assert(!nxt_get);
    nxt_get ^= 1;
#ifdef LOCAL
    steps++;
    cl = min((LD)1, max((LD)-1, cl + RandMean()));
    cr = min((LD)1, max((LD)-1, cr + RandMean()));
    REP (i, T) {
      Point pdir = {cos(dir), sin(dir)};
      LD coeff = (cl + cr) * V / (2 * T);
      cur = cur + pdir * coeff;
      dir += (cr - cl) * V / (2 * R * T);
    }
    debug(cur, dir);
    if (cur.Dist(pt[nxt_to_pass]) < R + S + L) {
      nxt_to_pass++;
      debug(nxt_to_pass);
    }
#else
    cout<<cl<<" "<<cr<<endl;
#endif
  };
  
  LD kSumThreshold = 1.80;
  LD kMaThreshold = 0.96;
  LD kDiffThreshold = 0.3;
  Get();
  while (1) {
    debug(sen1, sen2);
    LD sum = sen1 + sen2;
    LD ma = max(sen1, sen2);
    LD cp1 = sen1, cp2 = sen2;
    if (sum > kSumThreshold) {
      Go(1, 1);
      Get();
    } else if (ma > kMaThreshold || abs(sen1 - sen2) > kDiffThreshold) {
      if (sen2 > sen1) {
        Go(0, 0.5);
      } else {
        Go(0.5, 0);
      }
      Get();
      cerr<<"after return "<<sen1<<" "<<sen2<<" from "<<prv1<<" "<<prv2<<endl;
    } else {
      LD rcos = L + sum - 1;
      LD coss = (rcos) / R;
      LD alfa = acos(min((LD)1, coss));
      LD coeff = -100;
      LD diff_diff, new_diff, diff;
      while (coeff < -10 || coeff > 10) {
        diff = sen1 - sen2;
        int need_another_try = 1;
        while (need_another_try) {
          Go(-0.3, -0.3);
          Get();
          if (sen1 > prv1 - 0.03 && sen2 > prv2 - 0.03) {
            debug("rush");
            Go(1, 1);
            Get();
            goto End;
          } else {
            need_another_try = 0;
          }
        }
        cerr<<"badanie diff ";
        debug(sen1, sen2, prv1, prv2);
        new_diff = sen1 - sen2;
        diff_diff = new_diff - diff;
        coeff = -new_diff / diff_diff;
        if (coeff < -10 || coeff > 10) {
          Go(0.3, 0.3);
          Get();
          cerr<<"failed badanie diff"<<endl;
        }
      }
      assert(coeff > -10 && coeff < 10);
      LD to_go = abs(0.3 * coeff);
      while (to_go > kEps) {
        LD part = min(to_go, (LD)1);
        if (coeff > 0) {
          Go(-part, -part);
        } else {
          Go(part, part);
        }
        Get();
        to_go -= part;
      }
      LD x = R * alfa / V;
      debug(diff, new_diff, diff_diff, coeff, alfa, x);
      cerr<<"after positioning: "<<sen1<<" "<<sen2<<" from "<<cp1<<" "<<cp2<<endl;
      cp1 = sen1;
      cp2 = sen2;
      while (x > kEps) {
        
        LD part = min(x, (LD)1);
        if (diff_diff > 0) {
          Go(-part, part);
        } else {
          Go(part, -part);
        }
        x -= part;
        Get();
      }
      cerr<<"after turn: "<<sen1<<" "<<sen2<<" from "<<cp1<<" "<<cp2<<endl;
      //debug("after turn", sen1, sen2, );
    }
    End: ;

  }
    
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  return 0;
}