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 <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;
#define EPS (1e-10)

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;

struct Point { double x, y; };//点
struct Segment { Point p1, p2; };//線
class Circle {
public:
    Point c;
    double r;
    Circle(Point c = Point(), double r = 0.0) :c(c), r(r) {}
};
double dot(Point a, Point b) {//内積
    return a.x * b.x + a.y * b.y;
}
double cross(Point a, Point b) {//外積
    return a.x * b.y - a.y * b.x;
}
double norm(Point a) {
    return a.x * a.x + a.y * a.y;
}
double absv(Point a) {
    return sqrt(norm(a));
}
Point project(Segment s, Point p) {
    Point base, q;
    Point ans;
    base.x = s.p2.x - s.p1.x;
    base.y = s.p2.y - s.p1.y;
    q.x = p.x - s.p1.x;
    q.y = p.y - s.p1.y;
    double r = dot(q, base) / norm(base);
    ans.x = s.p1.x + base.x * r;
    ans.y = s.p1.y + base.y * r;
    return ans;
}
Point reflect(Segment s, Point p) {
    Point ans;
    ans.x = p.x + (project(s, p).x - p.x) * 2.0;
    ans.y = p.y + (project(s, p).y - p.y) * 2.0;
    return ans;
}
double getPointDistance(Point a, Point b) {
    Point ans;
    ans.x = a.x - b.x;
    ans.y = a.y - b.y;
    return absv(ans);
}
double getDistanceLP(Segment l, Point p) {
    Point tmp, tmp2;
    tmp.x = l.p2.x - l.p1.x;
    tmp.y = l.p2.y - l.p1.y;
    tmp2.x = p.x - l.p1.x;
    tmp2.y = p.y - l.p1.y;
    return abs(cross(tmp, tmp2) / absv(tmp));
}
double getDistanceSP(Segment s, Point p) {
    Point t1, t2, t3, t4;
    t1.x = s.p2.x - s.p1.x;
    t1.y = s.p2.y - s.p1.y;
    t2.x = p.x - s.p1.x;
    t2.y = p.y - s.p1.y;
    t3.x = s.p1.x - s.p2.x;
    t3.y = s.p1.y - s.p2.y;
    t4.x = p.x - s.p2.x;
    t4.y = p.y - s.p2.y;
    if (dot(t1, t2) < 0.0)return absv(t2);
    if (dot(t3, t4) < 0.0)return absv(t4);
    return getDistanceLP(s, p);
}
int ccw(Point p0, Point p1, Point p2) {
    Point a, b;
    a.x = p1.x - p0.x;
    a.y = p1.y - p0.y;
    b.x = p2.x - p0.x;
    b.y = p2.y - p0.y;
    if (cross(a, b) > EPS)return COUNTER_CLOCKWISE;
    if (cross(a, b) < (-EPS))return CLOCKWISE;
    if (dot(a, b) < (-EPS))return ONLINE_BACK;
    if (norm(a) < norm(b))return ONLINE_FRONT;

    return ON_SEGMENT;
}
bool intersect(Point p1, Point p2, Point p3, Point p4) {
    return(ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);
}
bool intersectS(Segment s1, Segment s2) {
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}
Point getCrossPoint(Segment s1, Segment s2) {
    Point base, a, b, c;
    base.x = s2.p2.x - s2.p1.x;
    base.y = s2.p2.y - s2.p1.y;
    a.x = s1.p1.x - s2.p1.x;
    a.y = s1.p1.y - s2.p1.y;
    b.x = s1.p2.x - s2.p1.x;
    b.y = s1.p2.y - s2.p1.y;
    double d1 = abs(cross(base, a));
    double d2 = abs(cross(base, b));
    double t = d1 / (d1 + d2);
    c.x = s1.p1.x + (s1.p2.x - s1.p1.x) * t;
    c.y = s1.p1.y + (s1.p2.y - s1.p1.y) * t;
    return c;
}
double getDistance(Segment s1, Segment s2) {
    if (intersectS(s1, s2))return 0.0;
    double a, b;
    a = min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2));
    b = min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2));
    return min(a, b);
}
pair<Point, Point> getCrossPoints(Circle c, Segment l) {
    Point a, b, z1, z2;
    a.x = l.p2.x - l.p1.x;
    a.y = l.p2.y - l.p1.y;
    Point pr = project(l, c.c);
    Point e;
    e.x = a.x / absv(a);
    e.y = a.y / absv(a);
    b.x = pr.x - c.c.x;
    b.y = pr.y - c.c.y;
    double base = sqrt(c.r * c.r - norm(b));
    z1.x = pr.x + e.x * base;
    z1.y = pr.y + e.y * base;
    z2.x = pr.x - e.x * base;
    z2.y = pr.y - e.y * base;
    return make_pair(z1, z2);
}
int main(void) {
    Circle a;
    Segment s;
    pair<Point, Point> ans;
    cin >> a.c.x >> a.c.y >> a.r;
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s.p1.x >> s.p1.y >> s.p2.x >> s.p2.y;
        ans = getCrossPoints(a, s);
        if (ans.first.x < ans.second.x) {
            cout << fixed << setprecision(8) << ans.first.x << " ";
            cout << fixed << setprecision(8) << ans.first.y << " ";
            cout << fixed << setprecision(8) << ans.second.x << " ";
            cout << fixed << setprecision(8) << ans.second.y << endl;
        }else if(ans.first.x == ans.second.x){
            if(ans.first.y<ans.second.y){
                cout << fixed << setprecision(8) << ans.first.x << " ";
                cout << fixed << setprecision(8) << ans.first.y << " ";
                cout << fixed << setprecision(8) << ans.second.x << " ";
                cout << fixed << setprecision(8) << ans.second.y << endl;
            }else{
                cout << fixed << setprecision(8) << ans.second.x << " ";
                cout << fixed << setprecision(8) << ans.second.y << " ";
                cout << fixed << setprecision(8) << ans.first.x << " ";
                cout << fixed << setprecision(8) << ans.first.y << endl;
            }
        }
        else {
            cout << fixed << setprecision(8) << ans.second.x << " ";
            cout << fixed << setprecision(8) << ans.second.y << " ";
            cout << fixed << setprecision(8) << ans.first.x << " ";
            cout << fixed << setprecision(8) << ans.first.y << endl;
        }
        
    }
    return 0;
}