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 <cmath>
#include <string>
#include <cstdio>
#include <algorithm>
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;

//点を表す構造体
class Point{
public:
  double x, y;

  Point(double x=0, double y=0){
    this->x = x;
    this->y = y;
  }

  Point operator+(const Point &seg2){
    return Point(x+seg2.x, y+seg2.y);
  }

  Point operator-(const Point &seg2){
    return Point(x-seg2.x, y-seg2.y);
  }

  Point operator*(const double k){
    return Point(x*k, y*k);
  }

  Point operator/(const double k){
    return Point(x/k, y/k);
  }

  Point &operator=(const Point &p){
    x = p.x;
    y = p.y;
    return *this;
  }

  bool operator < (const Point &p) const{
    return x != p.x? x<p.x : y<p.y;
  }

  bool operator == (const Point &p) const{
    return equals(x, p.x) && equals(y, p.y);
  }

  double norm(){
    return x*x + y*y;
  }

  double abs(){
    return sqrt(norm());
  }

  static double dot(Point a, Point b){
    return a.x*b.x + a.y*b.y;
  }

  static double cross(Point a, Point b){
    return a.x*b.y - a.y*b.x;
  }

  static bool isOrthogonal(Point a, Point b){
    return equals(dot(a, b), 0.0);
  }

  static bool isParallel(Point a, Point b){
    return equals(cross(a, b), 0.0);
  }

  static void swap(Point* a, Point* b){
    Point temp = *b;
    *b = *a;
    *a = temp;
  }
};

/*
//ベクトルを点の別表記でも表せるようにしておく
//いらない説濃厚(Pointのtypedefで済ませそう)
class Vector : public Point{
public:
  Vector() : Point() {}

  Vector(double x, double y) : Point(x, y) {}

  Vector(Point p) : Point(){
    x = p.x;
    y = p.y;
  }

  double norm(){
    return x*x + y*y;
  }

  double abs(){
    return sqrt(norm());
  }

  static double dot(Vector a, Vector b){
    return a.x*b.x + a.y*b.y;
  }

  static double cross(Vector a, Vector b){
    return a.x*b.y - a.y*b.x;
  }

  static bool isOrthogonal(Vector a, Vector b){
    return equals(dot(a, b), 0.0);
  }

  static bool isParallel(Vector a, Vector b){
    return equals(cross(a, b), 0.0);
  }
};
*/

typedef Point Vector;//Vectorをtypedefしておく

//線分(ベクトルを用いて)を表す構造体。両端の点が定義されている点に注意
class Segment{
public:
  Point p1, p2;

  Segment(Point p1, Point p2){
    this->p1 = p1;
    this->p2 = p2;
    x = p2.x-p1.x;
    y = p2.y-p1.y;
  }

  static bool isOrthogonal(Segment a, Segment b){
    return equals(dot(a, b), 0.0);
  }

  static bool isParallel(Segment a, Segment b){
    return equals(cross(a, b), 0.0);
  }

private:
  int x, y;
  static double dot(Segment a, Segment b){
    return a.x*b.x + a.y*b.y;
  }

  static double cross(Segment a, Segment b){
    return a.x*b.y - a.y*b.x;
  }
};

typedef Segment Line;

class Circle{
public:
  Point c;
  double r;
  Circle(Point c = Point(), double r = 0.0): c(c), r(r){}
};

class Polygon{
public:
  Point* ver;
  int size;
  Polygon(int size){
    this->size = size;
    ver = new Point[size];
  }
  ~Polygon(){
    delete[] ver;
  }

  double area(){
    double ans=0.0;

    Vector a, b;
    for(int i=0; i<size; i++){
      a=ver[i%size]; b=ver[(i+1)%size];
      ans += Vector::cross(a, b)/2;
    }

    return ans;
  }

  /*
    ・含まれる時:2
    ・辺上に点が存在する時:1
    ・それ以外の場合:0
    を返す
  */
  int contain(Point p){
    bool flag = false;

    int ans;
    for(int i=0; i<size; i++){
      Vector a = ver[i%size]-p, b = ver[(i+1)%size]-p;
      //外積=0かつ内積<0の時辺上に点があると判定できる
      if(fabs(Vector::cross(a, b))<EPS && Vector::dot(a, b)<EPS){
        ans = 1;
        return ans;
      }
      if(a.y > b.y)Vector::swap(&a, &b);
      //端点をうまく処理するために以下の条件分岐ではEPSの使い方に注意
      if(a.y < EPS && b.y > EPS && Vector::cross(a, b)>EPS) flag = !flag;
    }

    ans = flag ? 2 : 0;
    return ans;
  }
};

class Tryangle : public Polygon{
public:
  Tryangle(Point p1, Point p2, Point p3) : Polygon(3){
    ver[0] = p1;
    ver[1] = p2;
    ver[3] = p3;
  }
  double area(){
    Vector a = ver[1]-ver[0], b = ver[2]-ver[0];
    return fabs(Vector::cross(a, b))/2.0;
  }
};

string ccw_str(Point p0, Point p1, Point p2){
  //enum res {COUNTER_CLOCKWISE=0, CLOCKWISE, ONLINE_BACK, ONLINE_FRONT, ON_SEGMENT};
  Vector a = p1-p0;
  Vector b = p2-p0;
  if(Vector::cross(a, b) > EPS) return "COUNTER_CLOCKWISE";
  if(Vector::cross(a, b) < -EPS) return "CLOCKWISE";
  if(Vector::dot(a, b) < -EPS) return "ONLINE_BACK";
  if(a.norm() < b.norm()) return "ONLINE_FRONT";
  return "ON_SEGMENT";
}

int ccw_int(Point p0, Point p1, Point p2){
  enum res {COUNTER_CLOCKWISE=-1, CLOCKWISE=1, ONLINE_BACK=2, ONLINE_FRONT=-2, ON_SEGMENT=0};
  Vector a = p1-p0;
  Vector b = p2-p0;
  if(Vector::cross(a, b) > EPS) return COUNTER_CLOCKWISE;
  if(Vector::cross(a, b) < -EPS) return CLOCKWISE;
  if(Vector::dot(a, b) < -EPS) return ONLINE_BACK;
  if(a.norm() < b.norm()) return ONLINE_FRONT;
  return ON_SEGMENT;
}

Point project(Segment s, Point p){
  Vector base = s.p2-s.p1;
  double r = Vector::dot(p - s.p1, base) / base.norm();
  return s.p1 + base*r;
}

Point reflect(Segment s, Point p){
  Point pro = project(s, p);
  return p + (pro-p)*2.0;
}

bool intersect(Point p1, Point p2, Point p3, Point p4){
  return ccw_int(p1, p2, p3)*ccw_int(p1, p2, p4)<=0 && ccw_int(p3, p4, p1)*ccw_int(p3, p4, p2)<=0;
}

bool intersect(Segment s1, Segment s2){
  return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}

Point crossPoint(Point p1, Point p2, Point p3, Point p4){
  Vector base = p2-p1;
  double d1 = fabs(Vector::cross(base, p4-p1))/fabs(base.abs());
  double d2 = fabs(Vector::cross(base, p3-p1))/fabs(base.abs());
  double t = d1/(d1+d2);
  Point x = p4 + (p3-p4)*t;
  return x;
}

double getDistance(Point p1, Point p2){
  Vector base=p2-p1;
  return base.abs();
}

double getDistance(Point p, Segment s){
  double dot1, dot2;
  Vector base = s.p2-s.p1;
  dot1 = Vector::dot(base, p-s.p1);
  dot2 = Vector::dot(base*(-1.0), p-s.p2);

  double ans;
  if(dot1<-EPS) ans = getDistance(s.p1, p);
  else if(dot2<-EPS) ans = getDistance(s.p2, p);
  else ans = fabs(Vector::cross(p-s.p1, base))/base.abs();

  return ans;
}

double getDistance(Segment s1, Segment s2){
  double ans;
  if(intersect(s1, s2)) ans = 0.0;
  else {
    ans = min(min(getDistance(s1.p1, s2), getDistance(s1.p2, s2)),
                  min(getDistance(s2.p1, s1), getDistance(s2.p2, s1)));
  }
  return ans;
}

pair<Point, Point> getCrossPoints(Circle c, Line l){
  Point pr = project(l, c.c);
  Vector e = (l.p1-l.p2)/(l.p1-l.p2).abs();
  double base = sqrt(c.r*c.r - (pr-c.c).norm());

  pair<Point, Point> ans;
  Point a=pr+e*base, b=pr-e*base;
  ans = a<b? make_pair(a, b) : make_pair(b, a);
  return ans;
}

int main(){
  double cx, cy, cr;
  cin >> cx >> cy >> cr;
  Circle c(Point(cx, cy), cr);

  int q; cin >> q;

  double x1, y1, x2, y2;
  pair<Point, Point> ans;
  for(int i=0; i<q; i++){
    cin >> x1 >> y1 >> x2 >> y2;
    Line l(Point(x1, y1), Point(x2, y2));
    ans = getCrossPoints(c, l);
    printf("%.10lf %.10lf %.10lf %.10lf\n", ans.first.x, ans.first.y,
                                              ans.second.x, ans.second.y);
  }

  return 0;
}