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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

typedef double P_type;
typedef complex<P_type> P;
const P_type P_eps = 1e-10; //??´??°???????????????

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

bool operator==(const P &a, const P &b){
  const double eps = P_eps;
  return abs(a.real() - b.real()) <= eps && abs(a.imag() - b.imag()) <= eps;
}

P rotate(P p, double theta){
  return p * P(cos(theta), sin(theta));
}

//??????
double dot(P a, P b) {
  return (a * conj(b)).real();
}

//??????
double cross(P a, P b) {
  return (a * conj(b)).imag();
}

int ccw(P a, P b, P c){
  if(cross(b-a,c-a) > P_eps) return 1; //COUNTER_CLOCKWISE
  if(cross(b-a,c-a) < P_eps) return -1; //CLOCKWISE
  if(dot(b-a,c-a) < P_eps) return -2; //c -> a -> b
  if(dot(a-b,c-b) < P_eps) return 2; //a -> b -> c
  return 0; //a -> c -> b
}

/* ??????ab??¨???c????????¢ */
double distanceSP(P a, P b, P c) {
  if ( dot(b-a, c-a) < P_eps ) return abs(c-a);
  if ( dot(a-b, c-b) < P_eps ) return abs(c-b);
  return abs(cross(b-a, c-a)) / abs(b-a);
}

/* ??´???ab??¨???c????????¢ */
double distanceLP(P a, P b, P c) {
  return abs(cross(b-a, c-a)) / abs(b-a);
}

/* ????????????????????? */
double isContainedCP(P c, double r, P p){
  return abs(c-p) < r - P_eps; //?????¨??????????????????
  //return abs(c-p) < r + P_eps; //?????¨????????????
}

/* ??´??????????????? */
bool isIntersectedLL(P a1, P a2, P b1, P b2){
  return abs(cross(a1-a2, b1-b2)) > P_eps;
}

/* ?????????????????? */
bool isIntersectedSS(P a1, P a2, P b1, P b2){
  
  //??????a ??¨ ??´???b
  P_type a = ccw(b1,b2,a1);
  P_type b = ccw(b1,b2,a2);
  
  //??????b ??¨ ??´???a
  P_type c = ccw(a1,a2,b1);
  P_type d = ccw(a1,a2,b2);
  
  return a*b < P_eps && c*d < P_eps; // T?????????????????? -P_eps
}

/* ??????????????? */
bool isIntersectedCC(P c1, double r1, P c2, double r2){
  double dist = abs(c1 - c2);
  
  return abs(r1 - r2) < dist + P_eps && dist - P_eps < r1 + r2; //?????\?????\?????????
  //return abs(r1 - r2) < dist - P_eps && dist + P_eps < r1 + r2; //?????\?????\?????????
}

/* ?????´??????????????? */
bool isIntersectedCL(P c, double r, P a1, P a2){
  return distanceLP(a1, a2, c) < r + P_eps; //??\????????´????????????????????´??? - P_eps
}

/* ????????????????????? */
bool isIntersectedCS(P c, double r, P a1, P a2){
  return isContainedCP(c,r,a1) &&
    isContainedCP(c,r,a2) &&
    distanceLP(a1, a2, c) < r + P_eps; //??\????????´????????????????????´??? - P_eps
}

/* ??´???/???????????? */
P getCrosspointLL(P a1, P a2, P b1, P b2) {
  //assert(isIntersectedLL(a1, a2, b1, b2));
  //assert(isIntersectedSS(a1, a2, b1, b2));
  P a = a2 - a1;
  P b = b2 - b1;
  return a1 + a * cross(b, b1-a1) / cross(b, a);
}

P getCrosspointSS(P a1, P a2, P b1, P b2){
  return getCrosspointLL(a1, a2, b1, b2);
}

/* ????????? */
pair<P,P> getCrosspointCC(P c1, double r1, P c2, double r2){
  //assert(isIntersectedCC(c1, r1, c2, r2));
  
  double dist = abs(c1 - c2);
  double a = acos((r1*r1 + dist * dist - r2 * r2) / (2 * r1 * dist));
  return {c1 + polar(r1, arg(c2 - c1) + a), c1 + polar(r1, arg(c2 - c1) - a)};
}

/* ??????????????? */
pair<P,P> getCrosspointCS(P c, double r, P a1, P a2){
  //assert(isIntersectedCS(c1, r1, c2, r2));
  
  P base1 = a2 - a1;
  P proj = a1 + base1 * dot(c - a1, base1) / norm(base1); //?°???±
  P e = (a2 - a1) / abs(a2 - a1);
  P base2 = sqrt(r*r - norm(proj - c));
  return {proj + e*base2, proj - e*base2};
}


int main(){
  int cx,cy,r,q;

  scanf("%d%d%d%d",&cx,&cy,&r,&q);

  for(int i=0;i<q;i++){
    int x1,y1,x2,y2;

    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

    auto crosspoints = getCrosspointCS(P(cx,cy),r,P(x1,y1),P(x2,y2));

    if(crosspoints.second < crosspoints.first){
      swap(crosspoints.first, crosspoints.second);
    }

    printf("%.10lf %.10lf %.10lf %.10lf\n",
           crosspoints.first.real(),
           crosspoints.first.imag(),
           crosspoints.second.real(),
           crosspoints.second.imag());    
  }
    
  
  return 0;
}