//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>

using namespace std;

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<int> VI;
typedef vector<bool> VB;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef vector<VI> VVI;
typedef vector<VB> VVB;
typedef vector<VS> VVS;
typedef vector<VLL> VVLL;
typedef vector<VVI> VVVI;
typedef vector<VVLL> VVVLL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<int, string> PIS;
typedef pair<string, int> PSI;
typedef pair<string, string> PSS;


//数値・文字列
//------------------------------------------
inline int toInt(string s) {
    int v;
    istringstream sin(s);
    sin >> v;
    return v;
}

inline LL toLongLong(string s) {
    LL v;
    istringstream sin(s);
    sin >> v;
    return v;
}

template<class T>
inline string toString(T x) {
    ostringstream sout;
    sout << x;
    return sout.str();
}

inline VC toVC(string s) {
    VC data(s.begin(), s.end());
    return data;
}

template<typename List>
void SPRIT(const std::string &s, const std::string &delim, List &result) {
    result.clear();
    string::size_type pos = 0;
    while (pos != string::npos) {
        string::size_type p = s.find(delim, pos);
        if (p == string::npos) {
            result.push_back(s.substr(pos));
            break;
        } else {
            result.push_back(s.substr(pos, p - pos));
        }
        pos = p + delim.size();
    }
}

string TRIM(const string &str, const char *trimCharacterList = " \t\v\r\n") {
    string result;
    string::size_type left = str.find_first_not_of(trimCharacterList);
    if (left != string::npos) {
        string::size_type right = str.find_last_not_of(trimCharacterList);
        result = str.substr(left, right - left + 1);
    }
    return result;
}

template<typename T>
bool VECTOR_EXISTS(vector<T> vec, T data) {
    auto itr = std::find(vec.begin(), vec.end(), data);
    size_t index = distance(vec.begin(), itr);
    if (index != vec.size()) {
        return true;
    } else {
        return 0;
    }
}

#define UPPER(s) transform((s).begin(), (s).end(), (s).begin(), ::toupper)
#define LOWER(s) transform((s).begin(), (s).end(), (s).begin(), ::tolower)



//四捨五入 nLen=小数点第N位にする
//------------------------------------------

//切り上げ
double ceil_n(double dIn, int nLen) {
    double dOut;
    dOut = dIn * pow(10.0, nLen);
    dOut = (double) (int) (dOut + 0.9);
    return dOut * pow(10.0, -nLen);
}

//切り捨て
double floor_n(double dIn, int nLen) {
    double dOut;
    dOut = dIn * pow(10.0, nLen);
    dOut = (double) (int) (dOut);
    return dOut * pow(10.0, -nLen);
}

//四捨五入
double round_n(double dIn, int nLen) {
    double dOut;
    dOut = dIn * pow(10.0, nLen);
    dOut = (double) (int) (dOut + 0.5);
    return dOut * pow(10.0, -nLen);
}

//n桁目の数の取得
int take_a_n(int num, int n) {
    string str = toString(num);
    return str[str.length() - n] - '0';
}


//進数
//------------------------------------------

//"1111011" → 123
int strbase_2to10(const std::string &s) {
    int out = 0;
    for (int i = 0, size = s.size(); i < size; ++i) {
        out *= 2;
        out += ((int) s[i] == 49) ? 1 : 0;
    }
    return out;
}

//"123" → 1111011
int strbase_10to2(const std::string &s) {
    int binary = toInt(s);
    int out = 0;
    for (int i = 0; binary > 0; i++) {
        out = out + (binary % 2) * pow(static_cast<int>(10), i);
        binary = binary / 2;
    }
    return out;
}

//"ABC" 2748
int strbase_16to10(const std::string &s) {
    int out = stoi(s, 0, 16);
    return out;
}

//1111011 → 123
int intbase_2to10(int in) {
    string str = toString(in);
    return strbase_2to10(str);
}

//123 → 1111011
int intbase_10to2(int in) {
    string str = toString(in);
    return strbase_10to2(str);
}

int intbase_16to10(int in) {
    string str = toString(in);
    return strbase_16to10(str);
}

//123→ "7B"
string intbase_10to16(unsigned int val, bool lower = true) {
    if (!val)
        return std::string("0");
    std::string str;
    const char hc = lower ? 'a' : 'A';     // 小文字 or 大文字表記
    while (val != 0) {
        int d = val & 15;     // 16進数一桁を取得
        if (d < 10)
            str.insert(str.begin(), d + '0');  //  10未満の場合
        else //  10以上の場合
            str.insert(str.begin(), d - 10 + hc);
        val >>= 4;
    }
    return str;
}

//整数を2進数表記したときの1の個数を返す
LL bitcount64(LL bits) {
    bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);
    bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);
    bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);
    bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);
    bits = (bits & 0x0000ffff0000ffff) + (bits >> 16 & 0x0000ffff0000ffff);
    return (bits & 0x00000000ffffffff) + (bits >> 32 & 0x00000000ffffffff);
}



//comparison
//------------------------------------------
#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define C_MIN(a, b) ((a)<(b)?(a):(b))
#define C_ABS(a, b) ((a)<(b)?(b)-(a):(a)-(b))



//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define EACH(i, c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define COUNT(obj, v) count((obj).begin(), (obj).end(), v)
#define SEARCH(v, w) search((v).begin(), (v).end(), (w).begin(), (w).end())
#define B_SEARCH(obj, v) binary_search((obj).begin(), (obj).end(), v)
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define REVERSE(c) reverse((c).begin(), (c).end())
#define SUMI(obj) accumulate((obj).begin(), (obj).end(), 0)
#define SUMD(obj) accumulate((obj).begin(), (obj).end(), 0.)
#define SUMLL(obj) accumulate((obj).begin(), (obj).end(), 0LL)
#define SUMS(obj) accumulate((obj).begin(), (obj).end(), string())
#define UB(obj, n) upper_bound((obj).begin(), (obj).end(), n)
#define LB(obj, n) lower_bound((obj).begin(), (obj).end(), n)
#define PB push_back
#define MP make_pair




//input output
//------------------------------------------
#define GL(s) getline(cin, (s))
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define OUT(d) std::cout<<(d);
#define OUT_L(d) std::cout<<(d)<<endl;
#define FOUT(n, data) std::cout<<std::fixed<<std::setprecision(n)<<(data);
#define FOUT_L(n, data) std::cout<<std::fixed<<std::setprecision(n)<<(data)<<"\n";
#define EL() std::cout << "\n";
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v) {std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &vec) {
    for (T &x : vec) is >> x;
    return is;
}

template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {
    for (const T &x : vec) os << x << " ";
    return os;
}


//repetition
//------------------------------------------
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n)  FOR(i,0,n)
#define RREP(i, n) for(int i = n-1;i >= 0;i--)
#define FORLL(i, a, b) for(LL i=LL(a);i<LL(b);++i)
#define RFORLL(i, a, b) for(LL i=LL(b)-1;i>=LL(a);--i)
#define REPLL(i, n) for(LL i=0;i<LL(n);++i)
#define RREPLL(i, n) for(LL i=LL(n)-1;i>=0;--i)
#define FOREACH(x, v) for(auto &(x) : (v))
#define FORITER(x, v) for(auto (x) = (v).begin(); (x) != (v).end(); ++(x))


//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int MOD = 1000000007;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};


//math
//--------------------------------------------

//min <= aim <= max
template<typename T>
inline bool BETWEEN(const T aim, const T min, const T max) {
    if (min <= aim && aim <= max) {
        return true;
    } else {
        return false;
    }
}


template<class T>
inline T SQR(const T x) { return x * x; }

template<class T1, class T2>
inline T1 POW(const T1 x, const T2 y) {
    if (!y)return 1;
    else if ((y & 1) == 0) {
        return SQR(POW(x, y >> 1));
    } else return POW(x, y ^ 1) * x;
}


template<typename T>
constexpr T ABS(T x) {
    return x < 0 ? -x : x;
}

//partial_permutation nPr 順列
//first・・最初の数
//middle・・r(取り出す数)
//last・・n(全体数)
template<class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last) {
    reverse(middle, last);
    return next_permutation(first, last);
}

//combination nCr 組み合わせ
//first1・・最初の数
//last1==first2・・r(取り出す数)
//last2・・n(全体数)
template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator first1, BidirectionalIterator last1, BidirectionalIterator first2,
                      BidirectionalIterator last2) {
    if ((first1 == last1) || (first2 == last2)) {
        return false;
    }
    BidirectionalIterator m1 = last1;
    BidirectionalIterator m2 = last2;
    --m2;
    while (--m1 != first1 && !(*m1 < *m2)) {
    }
    bool result = (m1 == first1) && !(*first1 < *m2);
    if (!result) {
        while (first2 != m2 && !(*m1 < *first2)) {
            ++first2;
        }
        first1 = m1;
        std::iter_swap(first1, first2);
        ++first1;
        ++first2;
    }
    if ((first1 != last1) && (first2 != last2)) {
        m1 = last1;
        m2 = first2;
        while ((m1 != first1) && (m2 != last2)) {
            std::iter_swap(--m1, m2);
            ++m2;
        }
        std::reverse(first1, m1);
        std::reverse(first1, last1);
        std::reverse(m2, last2);
        std::reverse(first2, last2);
    }
    return !result;
}


//confirmation
//--------------------------------------------

//clear memory
#define CLR(arr, d) memset((arr), (d),sizeof(arr))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;



//平面幾何
//--------------------------------------------
//--------------------------------------------
//--------------------------------------------
//--------------------------------------------
//--------------------------------------------

//宣言
//--------------------------------------------

//long double or double
typedef double Real;

//ポイントクラス
typedef complex<Real> Point;

//線分クラス
typedef pair<Point, Point> Line;

//円
typedef pair<Point, Real> Circle;

//ポリゴン
typedef vector<Point> Poly;


//x座標優先で比較する
namespace std {
    bool operator<(const Point &a, const Point &b) {
        return real(a) == real(b) ? imag(a) < imag(b) : real(a) < real(b);
    }
}


//doubleの誤差
#define EPS (1e-4)
//double同士の比較
#define EQ(a, b) (abs((a)-(b)) < EPS)
//Pointの比較
#define EQP(a, b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )


//角度
//--------------------------------------------
Real toRadian(double degree) {
    return degree * PI / 180.0;
}

Real toDegree(double radian) {
    return radian * 180.0 / PI;
}







//内積・外積・単位・法線
//--------------------------------------------

//ベクトルpの向きの単位ベクトルを返す
Point unit_vector(Point p) {
    return p / abs(p);
}


//pの法線ベクトルを両方返す
pair<Point, Point> norm_vectors(Point p) {
    return make_pair(p * Point(0, 1), p * Point(0, -1));
}

//ベクトルを反時計に回す sはラジアン
Point rotate_vector(Point v, double s) {
    return Point(v.real() * cos(s) - v.imag() * sin(s), v.real() * sin(s) + v.imag() * cos(s));
}

//内積 a・b = |a||b|cosθ
inline double dot(const Point &a, const Point &b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}

//外積 a×b = |a||b|sinθ
inline double cross(const Point &a, const Point &b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}


//三角形　角度・面積
//--------------------------------------------
//3点a, b, cのおける、角bacを返す
Real args_bac(Point a, Point b, Point c) {
    return acos(dot(b - a, c - a) / (abs(b - a) * abs(c - a)));
}

//各辺の長さがa, b, cの三角形の、aの対角の角度を返す
Real args_bac(Real a, Real b, Real c) {
    return acos((b * b + c * c - a * a) / (2 * b * c));
}

//三角形の面積
Real heron_area(Real a, Real b, Real c) {
    Real s = (a + b + c) / 2;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}

//Real heron_area(Point a, Point b, Point c) {
//    b -= a;
//    c -= a;
//    return (cross(b, c) / 2.0);
//}

//三角形の重心
Point centerOfGravity(Point a, Point b, Point c) {
    return Point((a.real() + b.real() + c.real()) / 3.0, (a.imag() + b.imag() + c.imag()) / 3.0);
}

//三角形の外接円の半径
Real circumScribedCircleRadius(Point a, Point b, Point c) {
    Real edgeA = abs(b - c);
    Real angleA = args_bac(a, b, c);
    return (edgeA / sin(angleA) / 2.0);
}

//三角形の外接円の中心座標　外心
Point circumScribedCircleXY(Point a, Point b, Point c) {
    Real angleA = args_bac(a, b, c);
    Real angleB = args_bac(b, a, c);
    Real angleC = args_bac(c, a, b);
    Real A = sin(2.0 * angleA);
    Real B = sin(2.0 * angleB);
    Real C = sin(2.0 * angleC);
    Point point((a.real() * A + b.real() * B + c.real() * C) / (A + B + C),
                (a.imag() * A + b.imag() * B + c.imag() * C) / (A + B + C));
    return point;
}

//三角形が点Pを含むか
bool point_in_triangle(Point a, Point b, Point c, Point p) {
    Point ab = b - a;
    Point bp = p - b;

    Point bc = c - b;
    Point cp = p - c;

    Point ca = a - c;
    Point ap = p - a;

    Real c1 = cross(ab, bp);
    Real c2 = cross(bc, cp);
    Real c3 = cross(ca, ap);

    //内側
    if ((c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0)) {
        return true;
    } else {
        return false;
    }

}


//直線・線分
//--------------------------------------------

//頂点a, b, cの位置関係判定
//別名ccw couter-clock-wise
int points_relation(Point a, Point b, Point c) {
    b -= a;
    c -= a;
    if (cross(b, c) > EPS) return 1; //counter-clockwise
    if (cross(b, c) < -EPS) return -1; //clockwise
    if (dot(b, c) < -EPS) return 2; //c--a--b on line
    if (abs(b) < abs(c)) return -2; //a--b--c on line
    return 0; //on segment
}

//2直線の直行判定 Point版
bool is_orthogonal(Point a1, Point a2, Point b1, Point b2) {
    return EQ(dot(a1 - a2, b1 - b2), 0.0);
}

//2直線の直行判定 Line版
bool is_orthogonal(Line line1, Line line2) {
    return EQ(dot(line1.first - line1.second, line2.first - line2.second), 0.0);
}

//2直線の平行判定 Point版
bool is_parallel(Point a1, Point a2, Point b1, Point b2) {
    return EQ(cross(a1 - a2, b1 - b2), 0.0);
}

//2直線の平行判定 Line版
bool is_parallel(Line line1, Line line2) {
    return EQ(cross(line1.first - line1.second, line2.first - line2.second), 0.0);
}

//点cが**直線**a-b上にあるか
bool is_point_on_long_line(Point a, Point b, Point c) {
    return EQ(cross(b - a, c - a), 0.0);
}

//点cが**線分**a-b上にあるか
bool is_point_on_line(Point a, Point b, Point c) {
    return (abs(a - c) + abs(c - b) < abs(a - b) + EPS);
}

//点a, bを通る**直線**と,点cとの距離d
double distance_longline_point(Point a, Point b, Point c) {
    return abs(cross(b - a, c - a)) / abs(b - a);
}

//直線と点との距離　円用
Real line_dis(Line a, Point x) {
    return abs(cross(a.second - a.first, x - a.first)) / abs(a.second - a.first);
}

//点a, bを端点とする**線分**と、点cとの距離d
Real distance_line_point(Point a, Point b, Point c) {
    if (dot(b - a, c - a) < EPS) return abs(c - a);
    if (dot(a - b, c - b) < EPS) return abs(c - b);
    return abs(cross(b - a, c - a)) / abs(b - a);
}

//点a1, a2を端点とする線分と、点b1, b2を端点とする線分の交差判定
bool is_intersected_lines(Point a1, Point a2, Point b1, Point b2) {
    return (points_relation(a1, a2, b1) * points_relation(a1, a2, b2) <= 0 &&
            points_relation(b1, b2, a1) * points_relation(b1, b2, a2) <= 0);
}

//点a1, a2を端点とする線分と、点b1, b2を端点とする線分の距離
Real distance_line_line(Point a1, Point a2, Point b1, Point b2) {
    if (is_intersected_lines(a1, a2, b1, b2)) {
        return 0;
    } else {
        return min({
                           distance_line_point(a1, a2, b1),
                           distance_line_point(a1, a2, b2),
                           distance_line_point(b1, b2, a1),
                           distance_line_point(b1, b2, a2)
                   });
    }
}

//点a1, a2を端点とする線分と、点b1, b2を端点とする線分の交点
Point intersection_lines_point(Point a1, Point a2, Point b1, Point b2) {
    Point b = b2 - b1;
    double d1 = abs(cross(b, a1 - b1));
    double d2 = abs(cross(b, a2 - b1));
    double t = d1 / (d1 + d2);
    return a1 + (a2 - a1) * Point(t, 0);
}

//点a1, a2を通る直線と点b1, b2を通る直線の交点計算
Point intersection_longlines_point(Point a1, Point a2, Point b1, Point b2) {
    Point a = a2 - a1;
    Point b = b2 - b1;
    return a1 + a * Point(cross(b, b1 - a1), 0) / Point(cross(b, a), 0);
}


//直線a-bに点pから垂線をおろしたときの交点
Point projection_point(Point a, Point b, Point p) {
    Real t = dot(p - a, a - b) / (abs(a - b) * abs(a - b));
    return a + (a - b) * t;
}

//点pを線対称移動させる
Point reflection_point(Point a, Point b, Point p) {
    return p + (projection_point(a, b, p) - p) * (Real) 2.0;
}


//多角形
//--------------------------------------------

//面積を返す 反時計回りに整列させておく
//正なら反時計回り　負なら時計回り
Real poly_area(Poly p) {
    if (p.size() < 3)return 0;
    Real res = cross(p[p.size() - 1], p[0]);
    for (int i = 1; i < p.size(); i++) {
        res += cross(p[i - 1], p[i]);
    }
    return abs(res) / 2;
}

//凸多角形か判定する
//凸出ない場合、各辺から次の辺までの
//時計回り・反時計回りに反対のものが出てくる
bool is_convec_poly(Poly p) {
    if (p.size() < 3) {
        return false;
    }

    //sはstartのs　最初の回り方を保存する
    int s = -3;
    for (int i = 0; i < p.size(); i++) {
        //2辺隣接した辺を選ぶ
        int r = points_relation(p[i], p[(i != 0 ? i - 1 : p.size() - 1)], p[(i + 1 != p.size() ? i + 1 : 0)]);

        //外積が1 時計回りか反時計なら更新
        if (abs(r) == 1 && s == -3) s = r;

        //sとrの積が-1なら異なる回り方が出てきている
        //すべて時計回りなら-1*-1=1 反時計なら1*1=1
        if (s * r == -1) return false;
    }
    return true;
}

//最遠点対　凸多角形で最も長い距離を返す
//凸包の後に使うとよい
Real longest_points_distance(Poly p) {
    int n = p.size();
    if (n == 2) {
        return abs(p[0] - p[1]);
    }

    int i = 0, j = 0;
    for (int k = 0; k < n; k++) {
        if (!(p[i] < p[k])) i = k;
        if (p[j] < p[k]) j = k;
    }

    Real res = 0;
    int si = i, sj = j;
    while (i != sj || j != si) {
        res = max(res, abs(p[i] - p[j]));
        if (cross(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j]) < 0) i = (i + 1) % n;
        else j = (j + 1) % n;
    }

    return res;
}

//凸包
vector<Point> convex_hull(vector<Point> v) {
    int n = v.size(), k = 0;
    sort(v.begin(), v.end());
    vector<Point> r(2 * n);
    for (int i = 0; i < n; i++) {
        while (k > 1 && cross(r[k - 1] - r[k - 2], v[i] - r[k - 1]) <= EPS) k--;
        r[k++] = v[i];
    }
    for (int i = n - 2, t = k; i >= 0; i--) {
        while (k > t && cross(r[k - 1] - r[k - 2], v[i] - r[k - 1]) <= EPS) k--;
        r[k++] = v[i];
    }
    r.resize(k - 1);
    return r;
}

//多角形をLine lで分割した際の左側の集合を返す
Point getcrosspointll(Line l1, Line l2) {
    double c1 = cross(l1.first, l1.second), c2 = cross(l2.first, l2.second);
    double de = (l1.first.imag() - l1.second.imag()) * (l2.first.real() - l2.second.real()) -
                (l2.first.imag() - l2.second.imag()) * (l1.first.real() - l1.second.real());
    double x = (l2.second.real() - l2.first.real()) * c1 + (l1.first.real() - l1.second.real()) * c2;
    double y = (l2.second.imag() - l2.first.imag()) * c1 + (l1.first.imag() - l1.second.imag()) * c2;
    return Point(x / de, y / de);
}

Poly convexcut(Poly p, Line l) {
    int n = p.size();
    Poly q;

    for (int i = 0; i < n; i++) {
        if (points_relation(l.first, l.second, p[i]) != -1)q.push_back(p[i]);
        if (points_relation(l.first, l.second, p[i]) * points_relation(l.first, l.second, p[(i + 1) % n]) < 0.0) {
            if (!is_parallel(l, Line(p[i], p[(i + 1) % n]))) {
                q.push_back(getcrosspointll(l, Line(p[i], p[(i + 1) % n])));
            }
        }
    }
    return q;
}

//頂点pが多角形pの内外か判定する
//2･･･in 1･･･on 0･･･out
int point_in_poly(Poly v, Point p) {
    bool in = false;
    for (int i = 0; i < v.size(); ++i) {
        Point a = v[i] - p, b = v[(i + 1 != v.size() ? i + 1 : 0)] - p;
        if (a.imag() > b.imag()) swap(a, b);
        if (a.imag() <= EPS && EPS < b.imag() && cross(a, b) < -EPS) in = !in;
        if (cross(a, b) == 0 && dot(a, b) <= 0) return 1;
    }
    return in ? 2 : 0;
}



//円 第一引数は中点　第二引数は半径
//--------------------------------------------

//円の面積
Real circle_area(Circle c) {
    return PI * c.second * c.second;
}

//円の中に点xが内部にあるか
bool circle_in_x(Circle c, Point x) {
    return (abs(x - c.first) + EPS < c.second);
}

//円状に点xがあるか
bool circle_on_x(Circle c, Point x) {
    return EQ(abs(x - c.first), c.second);
}

//2つの円a, bの関係
int circle_relation(Circle a, Circle b) {
    double d = abs(a.first - b.first);

    if (a.second + b.second + EPS < d) return -1; //no cross point outside
    if (b.second + d + EPS < a.second) return 1; //no cross point(inside B in A)
    if (a.second + d + EPS < b.second) return 2; //no cross point(inside A in B)

    if (abs(a.second + b.second - d) < EPS) return -3; //one cross point(outside)
    if (abs(b.second + d - a.second) < EPS) return 3; //one cross point(inside B in A)
    if (abs(a.second + d - b.second) < EPS) return 4; //one cross point(inside A in B)

    return 0; //two cross point
}

//2円a, bの共通面積
Real intersection_area(Circle a, Circle b) {
    Real d = abs(a.first - b.first);

    if (a.second + b.second < d + EPS) return 0;

    //円aを半径が大きい方にする
    if (a.second < b.second) swap(a, b);

    //円bが円aに入ってたら
    if (b.second + d < a.second + EPS || b.second < EPS) return circle_area(b);

    Real t1 = args_bac(b.second, a.second, d);
    Real t2 = args_bac(a.second, b.second, d);
    Real tri = (a.second * a.second * sin(t1 * 2) + b.second * b.second * sin(t2 * 2)) / 2.0;
    return a.second * a.second * t1 + b.second * b.second * t2 - tri;
}

//2つの円の交点を返す
vector<Point> circle_inter_points(Circle a, Circle b) {
    vector<Point> v;
    int pos = circle_relation(a, b);
    if (pos == 0) {
        Real s = args_bac(b.second, abs(b.first - a.first), a.second);
        Point x = a.second * unit_vector(b.first - a.first);
        v.push_back(a.first + rotate_vector(x, s));
        v.push_back(a.first + rotate_vector(x, -s));
    } else if (abs(pos) >= 3) {
        v.push_back(a.first + a.second * unit_vector(b.first - a.first));
    }
    return v;
}

//円と直線の交点
pair<Point, Point> circle_inter_line_points(Circle c, Line l) {
    Real a=imag(l.first)-imag(l.second);
    Real b=real(l.second)-real(l.first);
    Real k=-b*imag(l.first)-a*real(l.first);

    Real d=a*real(c.first)+b*imag(c.first)+k;
    Real r=c.second;

    Real R=a*a+b*b;
    Real D=sqrt(R*r*r-d*d);
    Point p1=c.first+polar(1/sqrt(R), atan2(b, a))*Point(-d, D);
    Point p2=c.first+polar(1/sqrt(R), atan2(b, a))*Point(-d, -D);

    if (p2 < p1)
        swap(p1, p2);

    return make_pair(p1, p2);
//    vector<Point> v;
//    Real d = line_dis(l, a.first);
//    if (d < a.second + EPS) {
//        Point x = a.second * unit_vector(l.second - l.first);
//        if (points_relation(l.first, l.second, a.first) == 1) x = a.first + x * Point(0, -1);
//        else x = a.first + x * Point(0, 1);
//        if (d + EPS < a.second) {
//            Real y = sqrt(a.second * a.second - d * d);
//            if (d == 0) d += EPS;
//            Real s = args_bac(y, d, a.second);
//            v.push_back(rotate_vector(x, s));
//            v.push_back(rotate_vector(x, -s));
//        } else if (EQ(d, a.second)) {
//            v.push_back(x);
//        }
//    }
//    return v;
}

//点pを通る円cの接線
vector<Line> adjust_line(Circle c, Point p) {
    vector<Line> res;
    if (circle_in_x(c, p)) return res;
    if (circle_on_x(c, p)) {
        pair<Point, Point> n = norm_vectors(c.first - p);
        res.push_back(Line(n.first + p, p));
        return res;
    }
    Real x = c.second, z = abs(c.first - p);
    Real y = sqrt(z * z - x * x);
    Real s = args_bac(y, x, z);
    Point v = unit_vector(p - c.first) * c.second;

    res.push_back(Line(rotate_vector(v, s) + c.first, p));
    res.push_back(Line(rotate_vector(v, -s) + c.first, p));
    return res;
}

//円の共通接線を求める
vector<Line> common_adjust_line(Circle a, Circle b) {
    vector<Line> res;
    if (a.second + EPS < b.second) return common_adjust_line(b, a);
    if (EQ(a.first.real(), b.first.real()) && EQ(a.first.imag(), b.first.imag()) && EQ(a.second, b.second)) return res;

    Point pos = (b.first - a.first) * a.second / (a.second + b.second) + a.first;
    if (!circle_in_x(a, pos)) res = adjust_line(a, pos);

    if (EQ(a.second, b.second)) {
        pair<Point, Point> n = norm_vectors(unit_vector(b.first - a.first) * a.second);
        res.push_back(Line(a.first + n.first, b.first + n.first));
        res.push_back(Line(a.first + n.second, b.first + n.second));
    } else {
        Real c = abs(b.first - a.first);
        pos = unit_vector(b.first - a.first) * ((a.second * c) / (a.second - b.second)) + a.first;
        if (!circle_in_x(a, pos)) {
            vector<Line> tmp = adjust_line(a, pos);
            for (int i = 0; i < tmp.size(); i++) res.push_back(tmp[i]);
        }
    }

    return res;
}


//使い方
//--------------------------------------------

//xとyの取り出し型
//a.real(); //x
//a.imag(); //y

//単位ベクトル
//Point unit = a / abs(a);

//ベクトルの長さをk倍する
// a = a * Point(k, 0);

//ベクトルaのk倍の法線ベクトル
//P p1 = a * P(0, k);
//P p2 = a * P(0, -k);

//ベクトルaの単位法線ベクトル
//P p1 = (a * P(0, 1)) /abs(a);
//P p2 = (a * P(0, -1)) /abs(a);

/*
 *
 *
 *   ~~~~Below My Answer~~~~
 *
 *
 **/




int main() {

    double x, y, r;
    scanf("%lf %lf %lf", &x, &y, &r);
    Circle c(Point(x, y), r);

    size_t q;
    scanf("%zu", &q);

    for (size_t i=0; i<q; ++i) {
        double x, y;
        scanf("%lf %lf", &x, &y);
        Point p1(x, y);

        scanf("%lf %lf", &x, &y);
        Point p2(x, y);

        Line l(p1, p2);
        pair<Point, Point> ps=circle_inter_line_points(c, l);
        printf("%.9f %.9f ", real(ps.first), imag(ps.first));
        printf("%.9f %.9f\n", real(ps.second), imag(ps.second));
    }
}
























































Measured memory_bytes: 3716