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>
using namespace std;
typedef double db;
const db eps = 1e-12, pi = acos(-1);
int sign(db x) {return x < -eps ? -1 : x > eps;}
int cmp(db x, db y) {return sign(x - y);}
int intersect(db l1, db r1, db l2, db r2) {
    if (l1 > r1) swap(l1, r1); if (l2 > r2) swap(l2, r2); return cmp(r1, l2) != -1 && cmp(r2, l1) != -1;
}
int inmid(db k1, db k2, db k3) {return sign(k1 - k3) * sign(k2 - k3) <= 0;}//k3 in [k1,k2]?1:0
struct Point {
    db x, y;
    Point operator + (const Point & a)const {return Point{a.x + x, a.y + y};}
    Point operator - (const Point & a)const {return Point{x - a.x, y - a.y};}
    Point operator * (db a) const {return Point{x * a, y * a};}
    Point operator / (db a) const {return Point{x / a, y / a};}
    bool operator < (const Point p) const {int a = cmp(x, p.x); if (a) return a == -1; return cmp(y, p.y) == -1;}
    bool operator == (const Point & a) const {return cmp(x, a.x) == 0 && cmp(y, a.y) == 0;}
    db abs() {return sqrt(x * x + y * y);}
    db abs2() {return x * x + y * y;}
    db dis(Point p) {return ((*this) - p).abs();}
    db dis2(Point p) {return ((*this) - p).abs2();}
    int getP() const {return sign(y) == 1 || (sign(y) == 0 && sign(x) == -1);}
    void input() {scanf("%lf%lf", &x, &y);}
};
db cross(Point p1, Point p2) {return p1.x * p2.y - p1.y * p2.x;}
db cross(Point p0, Point p1, Point p2) {return cross(p1 - p0, p2 - p0);}
db dot(Point p1, Point p2) {return p1.x * p2.x + p1.y * p2.y;}
int inmid(Point k1, Point k2, Point k3) {return inmid(k1.x, k2.x, k3.x) && inmid(k1.y, k2.y, k3.y);}
bool compareangle(Point p1, Point p2) {//Polar Angle Sort
    return p1.getP() < p2.getP() || (p1.getP() == p2.getP() && sign(cross(p1, p2)) > 0);
}
int clockwise(Point p1, Point p2, Point p3) { // p1 p2 p3 anticlockwise:1 clockwise:-1 others:0
    return sign(cross(p1, p2, p3));
}
struct Line {
    Point s, e;
    void input() {scanf("%lf%lf%lf%lf", &s.x, &s.y, &e.x, &e.y);}
    Point vec() {return e - s;}
    db length() {return sqrt(dot(s - e, s - e));}
    db length2() {return dot(s - e, s - e);}
};
int onS(Line l, Point p) {// On Seg?
    return inmid(l.s, l.e, p) && sign(cross(l.s - p, l.e - l.s)) == 0;
}
bool checkLL(Line l1, Line l2) {
    return cmp(cross(l1.s, l2.s, l2.e), cross(l1.e, l2.s, l2.e)) != 0;
}
bool checkLS(Line l1, Line l2) {//Intersection of Line l1 and Seg l2?
    return sign(cross(l2.s, l1.s, l1.e)) * sign(cross(l2.e, l1.s, l1.e)) <= 0;
}
int checkSS(Line l1, Line l2) {//Intersection of Two Seg?1:0
    return intersect(l1.s.x, l1.e.x, l2.s.x, l2.e.x) && intersect(l1.s.y, l1.e.y, l2.s.y, l2.e.y) && checkLS(l1, l2) && checkLS(l2, l1);
}
Point project(Line l, Point p) {
    return l.s + l.vec() * dot(p - l.s, l.vec()) / l.length2();
}
Point reflect(Line l, Point p) {//Mirror Point
    return project(l, p) * 2 - p;
}
Point getLL(Line l1, Line l2) {//Intersection Point of Line l1,l2
    db w1 = cross(l2.s, l1.s, l2.e), w2 = cross(l2.s, l2.e, l1.e); return (l1.s * w2 + l1.e * w1) / (w1 + w2);
}
db disSP(Line l, Point p) {
    Point p2 = project(l, p);
    if (inmid(l.s, l.e, p2)) return p.dis(p2); else return min(p.dis(l.s), p.dis(l.e));
}
db disSS(Line l1, Line l2) {
    if (checkSS(l1, l2)) return 0;
    return min(min(disSP(l1, l2.s), disSP(l1, l2.e)), min(disSP(l2, l1.s), disSP(l2, l1.e)));
}
db area(vector<Point> A) {//Anticlockwise
    db ans = 0;
    for (int i = 0; i < A.size(); i++) ans += cross(A[i], A[(i + 1) % A.size()]);
    return ans / 2;
}
int contain(vector<Point>A, Point p) {//2:in 1:on 0:out
    int ans = 0; A.push_back(A[0]);
    for (int i = 1; i < A.size(); i++) {
        Line l = {A[i - 1], A[i]};
        if (onS(l, p)) return 1; if (cmp(l.s.y, l.e.y) > 0) swap(l.s, l.e);
        if (cmp(l.s.y, p.y) >= 0 || cmp(l.e.y, p.y) < 0) continue;
        if (sign(cross(l.e, l.s, p)) < 0)ans ^= 1;
    }
    return ans << 1;
}
bool checkconvex(vector<Point>A) { //anticlock
    int n = A.size(); A.push_back(A[0]); A.push_back(A[1]);
    for (int i = 0; i < n; i++) if (sign(cross(A[i], A[i + 1], A[i + 2])) == -1) return 0;
    return 1;
}
vector<Point> ConvexHull(vector<Point>A, int flag = 1) { // flag=0 不严格 flag=1 严格
    int n = A.size(); vector<Point>ans(n * 2);
    sort(A.begin(), A.end()); int now = 0; if (n <= 1)return A;
    for (int i = 0; i < n; ans[now++] = A[i++])
        while (now > 1 && sign(cross(ans[now - 2], ans[now - 1], A[i])) < flag)--now;
    for (int i = n - 2, pre = now; i >= 0; ans[now++] = A[i--])
        while (now > pre && sign(cross(ans[now - 2], ans[now - 1], A[i])) < flag)--now;
    ans.resize(now - 1); return ans;
}
db convexDiameter(vector<Point>A) {
    int n = A.size(); if (n <= 1)return 0;
    int is = 0, js = 0; for (int k = 1; k <= n; ++k)is = A[k] < A[is] ? k : is, js = A[js] < A[k] ? k : js;
    int i = is, j = js; db ret = A[i].dis(A[j]); do {
        if (sign(cross(A[(i + 1) % n] - A[i], A[(j + 1) % n] - A[j])) >= 0)(++j) %= n;
        else (++i) %= n;
        ret = max(ret, A[i].dis(A[j]));
    } while (i != is || j != js);
    return ret;
}
vector<Point> convexcut(vector<Point>A, Line l) { // 保留 k1,k2,p 逆时针的所有点,判断n是否为0
    int n = A.size(); A.push_back(A[0]); vector<Point>ans;
    for (int i = 0; i < n; i++) {
        int w1 = clockwise(l.s, l.e, A[i]), w2 = clockwise(l.s, l.e, A[i + 1]);
        if (w1 >= 0) ans.push_back(A[i]);
        if (w1 * w2 < 0) ans.push_back(getLL(l, Line{A[i], A[i + 1]}));
    }
    return ans;
}
struct Circle {
    Point o; db r;
    void input() {o.input(); scanf("%lf", &r);}
};
int checkCC(Circle c1, Circle c2) {// 返回两个圆的公切线数量
    db d = c1.o.dis(c2.o); if (cmp(d, c1.r + c2.r) == 1)return 4;
    if (cmp(d, c1.r + c2.r) == 0)return 3; if (cmp(d, abs(c1.r - c2.r)) == 1)return 2;
    if (cmp(d, abs(c1.r - c2.r)) == 0)return 1; return 0;
}
vector<Point> getCL(Circle c, Line l) {// 沿着 s->e 方向给出 , 相切给出两个
    Point p = project(l, c.o); db d = c.r * c.r - p.dis2(c.o);
    if (sign(d) == -1)return{};
    Point del = l.vec() / l.length() * sqrt(max(db(0.0), d)); return {p - del, p + del};
}
int main() {
    Circle c;c.input();
    int Q;cin>>Q;while(Q--){
        Line l;l.input();
        vector<Point> ANS=getCL(c,l);
        sort(ANS.begin(),ANS.end());
        printf("%.10lf %.10lf %.10lf %.10lf\n",ANS[0].x,ANS[0].y,ANS[1].x,ANS[1].y);
    }
}