円と直線の交点

円 $c$ と直線 $l$ の交点を求めてください。

入力

入力は以下の形式で与えられます。

$cx\; cy\; r$
$q$
$Line_1$
$Line_2$
:
$Line_q$

１行目に円の中心の座標 $cx$, $cy$, 半径 $r$ が与えられます。２行目にクエリの数 $q$ が与えられます。 続く $q$ 行に、クエリとして $q$ 個の直線 $Line_i$ が次の形式で与えられます。

$x_1\; y_1\; x_2\; y_2$

各直線はそれが通る２点 $p1$、$p2$ で表され、$x1$, $y1$ が $p1$ の座標、$x2$, $y2$ が $p2$ の座標を表します。入力はすべて整数で与えられます。

出力

各クエリごとに交点の座標を出力してください。

２つの交点の座標を以下の規則に従い空白区切りで出力してください。

• ただ１つの交点を持つ場合も同じ座標を２つ出力する。
• $x$ 座標が小さいものを先に出力する。$x$ 座標が同じ場合は $y$ 座標が小さいものを先に出力する。

出力は 0.000001 以下の誤差を含んでもよいものとします。

制約

• $p1$ と $p2$ は異なる。
• 円と直線は必ず交点を持つ。
• $1 \leq q \leq 1,000$
• $-10,000 \leq cx, cy, x1, y1, x2, y2 \leq 10,000$
• $1 \leq r \leq 10,000$

入出力例

入力例

2 1 1
2
0 1 4 1
3 0 3 3

出力例

1.00000000 1.00000000 3.00000000 1.00000000
3.00000000 1.00000000 3.00000000 1.00000000

Note

      解説      

---