Problem: For given a circle $c$ and a line $l$, print the coordinates of the cross points of them.

Constraints

* $p1$ and $p2$ are different
* The circle and line have at least one cross point
* $1 \leq q \leq 1,000$
* $-10,000 \leq cx, cy, x1, y1, x2, y2 \leq 10,000$
* $1 \leq r \leq 10,000$

Input

The input is given in the following format.

$cx\; cy\; r$
$q$
$Line_1$
$Line_2$
:
$Line_q$


In the first line, the center coordinate of the circle and its radius are given by $cx$, $cy$ and $r$. In the second line, the number of queries $q$ is given.

In the following $q$ lines, as queries, $Line_i$ are given ($1 \leq i \leq q$) in the following format.

$x_1\; y_1\; x_2\; y_2$

Each line is represented by two points $p1$ and $p2$ which the line crosses. The coordinate of $p1$ and $p2$ are given by ($x1$, $y1$) and ($x2$, $y2$) respectively. All input values are given in integers.

Output

For each query, print the coordinates of the cross points in the following rules.

* If there is one cross point, print two coordinates with the same values.
* Print the coordinate with smaller $x$ first. In case of a tie, print the coordinate with smaller $y$ first.



The output values should be in a decimal fraction with an error less than 0.000001.

Example

Input

2 1 1
2
0 1 4 1
3 0 3 3


Output

1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
//#include "GC_template.h"
using namespace std;

namespace CG{
    const double eps = 1e-8;
    int sgn(double x) {
        if (x < -eps) return -1;
        if (x > eps) return 1;
        return 0;
    }

    struct point {
        double x, y;
        point() = default;
        point(double x, double y) : x(x), y(y) {}
        point(const point &) = default;
    };

    typedef point vector;

    bool cmpx(const point &A, const point &B) {return A.x < B.x || (A.x == B.x && A.y < B.y);}
    point operator + (const point &A, const vector &B) {return point(A.x+B.x,A.y+B.y);}
    vector operator - (const point &A, const point &B) {return vector(A.x-B.x,A.y-B.y);}
    double operator * (const vector &A, const vector &B) {return A.x*B.x+A.y*B.y;}
    vector operator * (const vector &A, double r) {return vector(A.x*r,A.y*r);}
    vector operator * (double r, const vector &A) {return vector(A.x*r,A.y*r);}
    vector operator / (const vector &A, double r) {return vector(A.x/r,A.y/r);}
    double cross (const vector &A, const vector &B) {return A.x*B.y-A.y*B.x;}

    double sqr(double x) {return x*x;}
    double sqr_length(const vector &A) {return sqr(A.x)+sqr(A.y);}
    double length(const vector &A) {return sqrt(sqr_length(A));}
    double sqr_dist(const point &A,const point &B) {return sqr(A.x-B.x)+sqr(A.y-B.y);}
    double dist(const point &A,const point &B) {return sqrt(sqr_dist(A,B));}
    vector rot(const vector &A,double theta) {return vector(A.x*cos(theta)-A.y*sin(theta),A.x*sin(theta)+A.y*cos(theta));}
    vector lerp(const vector &A, const vector &B, double t) {return A*(1-t)+B*t;}
    int quadartic(double A, double B, double C,std::vector<double> &vec) {
        double det = sqr(B) - 4*A*C;
        if(det < 0) return 0;
        if(sgn(det) == 0) vec.push_back(-B/(2*A));
        else {
            vec.push_back((-B-sqrt(det))/(2*A));
            vec.push_back((-B+sqrt(det))/(2*A));
            if(A<0) std::swap(vec[0],vec[1]);
        }
        return vec.size();
    }

    struct segment {
        point a, b;
        vector v;
        segment() = default;
        segment(const point &a, const point &b) : a(a), b(b) { v = b - a; }
        segment(double x1, double y1, double x2, double y2) : a(x1, y1), b(x2, y2) { v = b - a; }
        segment(const segment &) = default;
    };

    typedef segment line;

    bool point_in_segment(const point &p, const segment &s) {
        return sgn(cross(s.b-s.a,p-s.a)) == 0 && sgn((p-s.a)*(p-s.b)) <= 0;
    }

    struct circle {
        point O;
        double r;
        circle() = default;
        circle(const point &O, double r) : O(O), r(r) {};
        circle(const circle &) = default;
    };
    const double pi = acos(-1);

    int get_tangents(const point &p, const circle &cir, std::vector<line> &vec) {
        vector u = p-cir.O;
        double l = dist(p,cir.O);
        if(sgn(l-cir.r) < 0) return 0;
        if(sgn(l-cir.r) == 0) {
            vec.emplace_back(p,p+rot(u,pi/2));
            return 1;
        }
        double theta = asin(cir.r/l);
        vec.emplace_back(p,p+rot(u,theta));
        vec.emplace_back(p,p+rot(u,-theta));
        return 2;
    }

    int get_tangents(circle A, circle B, std::vector<line> &vec) {
        if (A.r < B.r) std::swap(A, B);
        double l = dist(A.O, B.O);
        if (sgn(l) == 0 && sgn(A.r - B.r) == 0) return -1;
        if (sgn(A.r - B.r - l) > 0) return 0;
        if (sgn(A.r - B.r - l) == 0) {
            vec.emplace_back(lerp(A.O, B.O, A.r / l), rot(B.O - A.O, pi / 2));
            return 1;
        }

        {
            double theta = acos((A.r - B.r) / l);
            vector unit = (A.O - B.O) / l;
            vec.emplace_back(A.O + (A.r * rot(unit, theta)), B.O + (B.r * rot(unit, theta)));
            vec.emplace_back(A.O + (A.r * rot(unit, -theta)), B.O + (B.r * rot(unit, -theta)));
        }

        {
            if (sgn(A.r + B.r - l) > 0) return 2;
            if (sgn(A.r + B.r - l) == 0) {
                vec.emplace_back(lerp(A.O, B.O, A.r / l), rot(A.O - B.O, pi / 2));
                return 3;
            }
            double theta = acos((A.r + B.r) / l);
            vector unit = (A.O - B.O) / l;
            vec.emplace_back(A.O + (A.r * rot(unit, theta)), B.O + (B.r * rot(unit, theta)));
            vec.emplace_back(A.O + (A.r * rot(unit, -theta)), B.O + (B.r * rot(unit, -theta)));
            return 4;
        }
    }

    int circle_line_intersection(const circle &c, const line &l,std::vector<point> &vec) {
        vector d = l.v;
        double A = d * d, B = d * (l.a - c.O) * 2, C = sqr_dist(l.a, c.O) - sqr(c.r);
        std::vector<double> vect;
        int t = quadartic(A, B, C, vect);
        if (t == 0) return 0;
        for (auto v : vect)
            vec.emplace_back(lerp(l.a, l.b, v));
        return t;
    }

    int circle_circle_intersection(circle A, circle B,std::vector<point> &vec) {
        if (A.r < B.r) std::swap(A, B);
        double l = dist(A.O, B.O);
        if (sgn(l) == 0) {
            if (sgn(A.r - B.r) == 0) return -1;
            else return 0;
        }
        if (sgn(A.r + B.r - l) < 0 || sgn(A.r - B.r - l) > 0) return 0;
        double theta = acos((sqr(A.r) + sqr(l) - sqr(B.r)) / (2 * A.r * l));
        if (sgn(A.r + B.r - l) == 0) {
            vec.emplace_back(lerp(A.O, B.O, A.r / l));
            return 1;
        }
        vector unit = (A.O - B.O) / l;
        vec.emplace_back(A.r * rot(unit, theta));
        vec.emplace_back(A.r * rot(unit, -theta));
    }
}
int main() {
    CG::circle A;
    cin >> A.O.x >> A.O.y >> A.r;
    int t;
    cin >> t;
    while(t--) {
        double x1,x2,y1,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        CG::line l(x1,y1,x2,y2);
        vector<CG::point> vec;
        int t = CG::circle_line_intersection(A,l,vec);
        sort(vec.begin(),vec.end(),CG::cmpx);
        assert(t != 0);
        if(t == 1) {
            printf("%.12f %.12f ",vec[0].x,vec[0].y);
            printf("%.12f %.12f\n",vec[0].x,vec[0].y);
        }
        else {
            printf("%.12f %.12f ",vec[0].x,vec[0].y);
            printf("%.12f %.12f\n",vec[1].x,vec[1].y);
        }
    }
    return 0;
}