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;

using CP = complex<long double>;
#define X real()
#define Y imag()
const long double PI = acos(-1.0L);
const long double EPS = 1e-10;
// conj(x) : complex conjugate,(0,1)->(0,-1)
// abs(x) : dist between(0,0) and x
// norm(x) : abs(x) * abs(x)
// arg(x) : argment

// dot(a,b) = |a||b|cos x
long double dot(CP a, CP b) { return (a * conj(b)).X; }
// cross(a,b) : area of parallelogram
long double cross(CP a, CP b) { return (a * conj(b)).Y; }
long double corner(CP a, CP b) {
  //[0,pi]
  return acos(dot(a, b) / (abs(a) * abs(b)));
}
CP projection(CP p, CP s, CP t) {
  CP base = t - s;
  long double r = dot(p - s, base) / norm(base);
  return s + base * r;
}
CP reflection(CP p, CP s, CP t) {
  CP tmp = (projection(p, s, t) - p);
  tmp *= 2;
  return p + tmp;
}

CP intersection(CP a, CP b, CP c, CP d) {
  return a + (b - a) * (cross(d - c, c - a) /
                        cross(d - c, b - a));
}

bool on_seg(CP a, CP b, CP p) {
  // if not use end point, dot(a - p, b - p) < 0
  return abs(cross(a - p, b - p)) <= 1e-10 &&
         dot(a - p, b - p) <= 0;
}

// crossing lines? (a,b) and (c,d)
bool iscross(CP a, CP b, CP c, CP d) {
  // parallel
  if(abs(cross(a - b, c - d)) <= 1e-10) {
    return on_seg(a, b, c) || on_seg(a, b, d) ||
           on_seg(c, d, a) || on_seg(c, d, b);
  }
  CP isp = intersection(a, b, c, d);
  return on_seg(a, b, isp) && on_seg(c, d, isp);
}

long double distLP(CP a, CP b, CP p) {
  return abs(cross(b - a, p - a) / abs(b - a));
}

// segmentver.
long double distSP(CP a, CP b, CP p) {
  if(dot(b - a, p - a) < 0) return abs(p - a);
  if(dot(a - b, p - b) < 0) return abs(p - b);
  return distLP(a, b, p);
}

// segment and segment
long double distSS(CP a, CP b, CP c, CP d) {
  long double res = 1e18;
  if(iscross(a, b, c, d)) return 0.0L;
  res = min(res, distSP(a, b, c));
  res = min(res, distSP(a, b, d));
  res = min(res, distSP(c, d, a));
  res = min(res, distSP(c, d, b));
  return res;
}

struct convex_hull {
  vector<CP> ch;
  int psize;
  convex_hull() {}
  convex_hull(vector<CP> &ps) { calculation(ps); }
  void calculation(vector<CP> &ps) {
    auto lmd = [&](const CP &l, const CP &r) {
      if(l.X != r.X) return l.X < r.X;
      return l.Y < r.Y;
    };
    psize = ps.size();
    sort(ps.begin(), ps.end(), lmd);
    int k = 0;
    ch.resize(psize * 2);
    for(int i = 0; i < psize; ++i) {
      while(k > 1 && cross(ch[k - 1] - ch[k - 2],
                           ps[i] - ch[k - 1]) <= 0)
        --k;
      ch[k++] = ps[i];
    }
    for(int i = psize - 2, t = k; i >= 0; --i) {
      while(k > t && cross(ch[k - 1] - ch[k - 2],
                           ps[i] - ch[k - 1]) <= 0)
        --k;
      ch[k++] = ps[i];
    }
    ch.resize(k - 1);
    psize = ch.size();
  }
};

struct Circle {
  CP o;
  long double r;
  Circle(long double _x = 0.0L, long double _y = 0.0L,
         long double _r = 0.0L)
      : o(CP(_x, _y)), r(_r) {}
};

void intersectionCL(Circle ci, CP s, CP t, CP &res1,
                    CP &res2) {
  res1 = res2 = projection(ci.o, s, t);
  long double r = sqrtl(ci.r * ci.r - norm(res1 - ci.o));
  t -= s;
  t *= r / abs(t);
  res1 += t;
  res2 -= t;
  if(res1.X > res2.X ||
     (res1.X == res2.X && res1.Y > res2.Y))
    swap(res1, res2);
}

long long n, id = 0, a, b, c, d;
Circle ci;
CP s, t, res1, res2;

int main() {
  cout << fixed << setprecision(10);
  cin >> a >> b >> c;
  ci = Circle(a, b, c);
  cin >> n;
  for(int i = 0; i < n; ++i) {
    cin >> a >> b >> c >> d;
    s = CP(a, b);
    t = CP(c, d);
    intersectionCL(ci, s, t, res1, res2);
    cout << res1.X << " " << res1.Y << " " << res2.X << " "
         << res2.Y << endl;
  }
  return 0;
}