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;
const double inf = 1e20;
const double eps = 1e-8;
const int N = 2e5 + 100;
int sgn (double x) {
    if (fabs (x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}
struct point {
    double x, y;
    point () {}
    point (double _x, double _y) {
        x = _x, y = _y;
    }
    void input () {
        scanf ("%lf %lf", &x, &y);
    }
    point operator - (const point &b) const {
        return point (x - b.x, y - b.y);
    }
    bool operator == (const point &b) const {
        return sgn (x - b.x) == 0 && sgn (y - b.y) == 0;
    }
    bool operator < (const point &b) const {
        if (sgn (x - b.x) == 0) return y < b.y;
        return x < b.x;
    }
    double operator * (const point &b) const {
        return x * b.x + y * b.y;
    }
    double operator ^ (const point &b) const {
        return x * b.y - y * b.x;
    }
    point operator / (const double &b) const {
        return point (x / b, y / b);
    }
    point operator * (const double &b) const {
        return point (x * b, y * b);
    }
    point operator + (const point &b) const {
        return point (x + b.x, y + b.y);
    }
    double cross (point a, point b) {
        return (point (a - *this) ^ point (b - *this));
    }
    double dot (point a, point b) {
        return (point (a - *this) * point (b - *this));
    }
    double len () {
        return hypot (x, y);
    }
    bool on_seg (point a, point b) {///点是否在线段ab上
        return sgn (cross (a, b)) == 0 && dot (a, b) <= 0;
    }
} s, e;
///两线段的交点
point spp (point s1, point e1, point s, point e) {
    if (s.dot (e, s1) > s.dot (e, e1)) swap (s1, e1);
    point p = e - s;
    double len = p.len ();
    double a = fabs (s.cross (e, s1)) / len;
    double b = fabs (s.cross (e, e1)) / len;
    double a1 = s.dot (e, s1) / len;
    double b1 = s.dot (e, e1) / len;
    double k = a1 + fabs(a1 - b1) / (a + b) * a;
    p = p / len, p = p * k, p = p + s;
    return p;
}
///两线段是否相交
bool seg (point a, point b, point c, point d) {
    if (a.on_seg (c, d)) return true;
    if (a.cross (b, d) * a.cross (b, c) < 0 && c.cross (d, b) * c.cross (d, a) < 0) return true;
    return false;
}
/// 点的投影是否在线段ab上
bool check (point p, point a, point b) {
    point x = b - a;
    double k = x.len ();
    double u = a.dot (p, b) / k;
    x = (x / k) * u;
    x = x + a;
    if (x.on_seg (a, b)) return true;
    return false;
}
//struct polygon {
//    int n;
//    point ps[N];
//    void input () {
//        cin >> n;
//        for (int i = 0; i < n; i++) ps[i].input ();
//    }
//    ///排序规则
//    struct cmp {
//        point p;
//        cmp (point _p) {
//            p = _p;
//        }
//        bool operator () (const point &aa, const point &bb) {
//            point a = aa, b = bb;
//            int d = sgn (p.cross (a, b));
//            if (d == 0) return point (a - p).len () < point (b - p).len ();
//            else return d > 0;
//        }
//    };
//    ///排序
//    void norm () {
//        point mi = ps[0];
//        for (int i = 0; i < n; i++) mi = min (mi, ps[i]);
//        sort (ps, ps + n, cmp (mi));
//    }
//    ///求凸包
////    void getconvex (polygon &convex) {
////        sort (ps, ps + n);
////        int &top = convex.n;
////        top = 0;
////        convex.ps[top++] = ps[0];
////        for (int i = 1; i < n; i++) {
////            while (top >= 2 && convex.ps[top - 2].cross (convex.ps[top - 1], ps[i]) < 0) top--;
////            convex.ps[top++] = ps[i];
////        }
////        int t = 0;
////        for (int i = n - 2; i >= 0; i--) {
////            while (t && convex.ps[top - 2].cross (convex.ps[top - 1], ps[i]) < 0) top--, t--;
////            if (!i) break;
////            convex.ps[top++] = ps[i];
////            t++;
////        }
////    }
//    ///几何面积
//    double mianji () {
//        if (n < 2) return 0;
//        double ans = 0;
//        ps[n] = ps[0];
//        for (int i = 1; i <= n; i++) ans += point (0, 0).cross (ps[i - 1], ps[i]);
//        return ans;
//    }
//} dd, ans;
struct circle {
    point p;
    double r;
    circle () {}
    circle (point _p, double _r) {
        p = _p, r = _r;
    }
    void input () {
        p.input ();
        scanf ("%lf", &r);
    }
} cr;
int main () {
//    freopen ("in.txt", "r", stdin);
    int Q;
    cr.input ();
    cin >> Q;
    while (Q --) {
        s.input (), e.input ();
        double len = fabs (s.cross (e, cr.p)) / point (e - s).len ();
        if (sgn (len - cr.r) == 0) {
            point a = e - s;
            double u = a.len ();
            double k = s.dot (e, cr.p) / u;
            a = a / u * k;
            a = a + s;
//            cout << "****" << endl;
            printf ("%.8f %.8f %.8f %.8f\n", a.x, a.y, a.x, a.y);
            continue;
        }
        point a = e - s;
        double len1 = fabs (s.cross (e, cr.p)) / a.len ();
        double len2 = s.dot (e, cr.p) / a.len ();
        double u = sqrt (cr.r * cr.r - len1 * len1);
        double k1 = len2 - u, k2 = len2 + u, k3 = a.len ();
        point ans1 = a / k3 * k1;
        point ans2 = a / k3 * k2;
        ans1 = ans1 + s;
        ans2 = ans2 + s;
        if (ans2 < ans1) swap (ans1, ans2);
        printf ("%.8f %.8f %.8f %.8f\n", ans1.x, ans1.y, ans2.x, ans2.y);
    }
    return 0;
}