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>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
const int INF = 100000000;
using namespace std;


typedef complex<double> Point;
typedef Point Vector;
//???????????¨????§???????
struct Segment{ Point p1, p2; };
//??´????????¨????§???????
typedef Segment Line;
//????§???¢?????¨????§???????
typedef vector<Point> Polygon;

namespace std{
    bool operator < (const Point &a, const Point &b){
        return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
    }
    bool operator == (const Point &a, const Point &b){
        return a.real() == b.real() && a.imag() == b.imag();
    }
}

class Circle{
public:
    Point c;
    double r;
    Circle(Point c = Point(), double r = 0.0): c(c), r(r) {}
};

// ?¨±???????????????
#define EPS (1e-10)
// 2??????????????????????????????????????????
//#define EQ(a,b) (abs((a)-(b)) < EPS)
// 2??????????????????????????????????????????
//#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )

// ????????????a?????¶??????????±???????
//double length = abs(a);

// 2???a,b???????????¢????±???????
//double distance = abs(a-b);

/*
// ????????????a?????????????????????????±???????
Point b = a / abs(a);

// ????????????a?????????????????????n1,n2????±???????
Point n1 = a * Point(0, 1);
Point n2 = a * Point(0, -1);
*/

int ccw(Point, Point, Point);

// 2??????????????????????????????????????????
bool EQ(double a, double b){
    return (abs(a - b) < EPS);
}

// 2??????????????????????????????????????????
bool EQV(Vector a, Vector b){
    return ( EQ(a.real(), b.real()) && EQ(a.imag(), b.imag()) );
}

// ?????? (dot product) : a???b = |a||b|cos??
double dot(Point a, Point b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}

// ?????? (cross product) : a??b = |a||b|sin??
double cross(Point a, Point b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

// 2??´????????´????????? : a??\b <=> dot(a, b) = 0
bool isOrthogonal(Point a1, Point a2, Point b1, Point b2) {
    return EQ( dot(a1-a2, b1-b2), 0.0 );
}
bool isOrthogonal(Line s1, Line s2) {
    return isOrthogonal(s1.p1, s1.p2, s2.p1, s2.p2);
}

// 2??´?????????????????? : a//b <=> cross(a, b) = 0
bool isParallel(Point a1, Point a2, Point b1, Point b2) {
    return EQ( cross(a1-a2, b1-b2), 0.0 );
}
bool isParallel(Line s1, Line s2) {
    return isParallel(s1.p1, s1.p2, s2.p1, s2.p2);
}

// ???c?????´???a,b????????????????????????
bool isPointOnLine(Point a, Point b, Point c) {
    return EQ( cross(b-a, c-a), 0.0 );
}
bool isPointOnLine(Line s, Point c) {
    return isPointOnLine(s.p1, s.p2, c);
}

// ???a,b???????????´?????¨???c??¨????????¢
double distanceLPoint(Point a, Point b, Point c) {
    return abs(cross(b-a, c-a)) / abs(b-a);
}
double distanceLPoint(Line s, Point c) {
    return distanceLPoint(s.p1, s.p2, c);
}

// ???a,b???????????¨??????????????¨???c??¨????????¢
double distanceLsPoint(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);
}
double distanceLsPoint(Segment s, Point c) {
    return distanceLsPoint(s.p1, s.p2, c);
}

// a1,a2???????????¨??????????????¨b1,b2???????????¨???????????????????????????
bool isIntersectedLs(Point a1, Point a2, Point b1, Point b2) {
    return ( ccw(a1, a2, b1) * ccw(a1, a2, b2) <= 0 &&
             ccw(b1, b2, a1) * ccw(b1, b2, a2) <= 0 );
}
bool isIntersectedLs(Segment s1, Segment s2) {
    return isIntersectedLs(s1.p1, s1.p2, s2.p1, s2.p2);
}

// a1,a2???????????¨??????????????¨b1,b2???????????¨??????????????????????¨????
Point intersectionLs(Point a1, Point a2, Point b1, Point b2) {
    Vector base = b2 - b1;
    double d1 = abs(cross(base, a1 - b1));
    double d2 = abs(cross(base, a2 - b1));
    double t = d1 / (d1 + d2);

    return Point(a1 + (a2 - a1) * t);
}
Point intersectionLs(Segment s1, Segment s2) {
    return intersectionLs(s1.p1, s1.p2, s2.p1, s2.p2);
}

// a1,a2???????????´?????¨b1,b2???????????´??????????????????
bool isIntersectedL(Point a1, Point a2, Point b1, Point b2) {
    return !EQ( cross(a1-a2, b1-b2), 0.0 );
}
bool isIntersectedL(Line l1, Line l2) {
    return isIntersectedL(l1.p1, l1.p2, l2.p1, l2.p2);
}

// a1,a2???????????´?????¨b1,b2???????????´?????????????¨????
Point intersectionL(Point a1, Point a2, Point b1, Point b2) {
    Point a = a2 - a1; Point b = b2 - b1;
    return a1 + a * cross(b, b1-a1) / cross(b, a);
}
Point intersectionL(Line l1, Line l2) {
    return intersectionL(l1.p1, l1.p2, l2.p1, l2.p2);
}

// ??????s1??¨??????s2????????¢
double distanceLL(Segment s1, Segment s2){
    if(isIntersectedLs(s1.p1, s1.p2, s2.p1, s2.p2) ) return 0.0;
    return min(
            min(distanceLsPoint(s1.p1, s1.p2, s2.p1),
                distanceLsPoint(s1.p1, s1.p2, s2.p2)),
            min(distanceLsPoint(s2.p1, s2.p2, s1.p1),
                distanceLsPoint(s2.p1, s2.p2, s1.p2)) );
}

// ??????s???????????????p????°???±
Point project(Segment s, Point p){
    Vector base = s.p2 - s.p1;
    double r = dot(p - s.p1, base) / norm(base);
    return Point(s.p1 + base * r);
}

//??????s???????±??????¨?????????p??????????§°??????
Point reflect(Segment s, Point p){
    return Point(p + (project(s, p) - p) * 2.0);
}

//???p???angle?????????????¨???????????????¢
Point rotation(Point p, double angle){
    double x, y;
    x = p.real() * cos(angle) - p.imag() * sin(angle);
    y = p.real() * sin(angle) + p.imag() * cos(angle);
    return Point(x, y);
}

//???c??¨??????l?????????
pair<Point, Point> getCrossPoints(Circle c, Line l){
    Vector pr = project(l, c.c);
    Vector e = (l.p2 - l.p1) / abs(l.p2 - l.p1);
    double base = sqrt(c.r * c.r - norm(pr - c.c));
    return make_pair(pr + e * base, pr - e * base);
}

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw(Point p0, Point p1, Point p2){
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if( cross(a, b) > EPS ) return COUNTER_CLOCKWISE;
    if( cross(a, b) < -EPS ) return CLOCKWISE;
    if( dot(a, b) < -EPS ) return ONLINE_BACK;
    if( abs(a) < abs(b) ) return ONLINE_FRONT;

    return ON_SEGMENT;
}

int main(){
    int n;
    double cx, cy, r;
    cin >> cx >> cy >> r >> n;

    Circle c;
    c.c = Point(cx, cy);
    c.r = r;
    while(n--){
        double a[4];
        rep(i,4) cin >> a[i];

        pair<Point, Point> p;
        p = getCrossPoints(c, Line{Point(a[0], a[1]), Point(a[2], a[3])});

        vector<Point> v;
        v.emplace_back(p.first);
        v.emplace_back(p.second);
        sort(all(v));
        cout << fixed << setprecision(10);
        cout << v[0].real() << ' ' << v[0].imag() << ' ';
        cout << v[1].real() << ' ' << v[1].imag() << endl;
    }
}