ロードレースに参加している自転車選手は、初期時刻と呼ばれるある時刻に、スタート地点からそれぞれ $x_1,x_2,\ldots,x_n$ メートル離れた位置にいます（$n$ は選手の総数です）。各選手はそれぞれ一定の速度 $v_1,v_2,\ldots,v_n$ メートル毎秒で走ります。全員が同じ方向に進みます。

競技を取材している記者は、ヘリコプターから参加者全員を一度に撮影するため、先頭の選手と最後尾の選手との距離が最小になる時刻を求めたいと考えています。

選手の人数 $n$、初期位置 $x_1,x_2,\ldots,x_n$、速度 $v_1,v_2,\ldots,v_n$ が与えられたとき、先頭と最後尾の選手との距離 $l$ が最小になる時刻 $t$ を計算するプログラムを作成してください。

入力

入力ファイルの最初の行には、選手の人数を表す整数 $n$ が与えられます。

続く $n$ 行には、それぞれ 2 つの整数が与えられます。$x_i$ は初期時刻における選手 $i$ のスタート地点からの距離（$0\le x_i\le10^7$）、$v_i$ はその速度（$0\le v_i\le10^7$）です。

出力

出力ファイルに 2 つの実数を出力してください。$t$ は、初期時刻から、先頭と最後尾とのメートル単位の距離が最小になるまでの経過時間（秒）です。$l$ はその距離です。

$t$ と $l$ の絶対誤差または相対誤差は $10^{-6}$ 以下でなければなりません。つまり、出力した数を $x$、正しい答えを $y$ とすると、$|x-y|/\max\{1,|y|\}$ が $10^{-6}$ 以下なら正解とみなされます。

入出力例

入力 1

3
0 40
30 10
40 30

出力 1

1 30

入力 2

5
90 100
100 70
100 70
110 60
120 35

出力 2

0.5 5.000000000000

小課題

この課題には 4 つの小課題があります。各小課題は専用のテスト群で採点され、その群のすべてのテストに合格した場合にのみ得点が与えられます。

小課題 1 (20 点)

$2\le n\le50$、$0\le x_i\le1000$、$0\le v_i\le1000$。$t$ が $1000$ 以下の整数となる答えが存在することが保証されます。

小課題 2 (20 点)

$2\le n\le200$.

小課題 3 (30 点)

$2\le n\le2000$.

小課題 4 (30 点)

$2\le n\le10^5$.

フィードバック

競技中、審査用テストでのプログラムの実行結果を最大 10 回問い合わせることができます。問い合わせは 5 分に 1 回までです。各テストについて、そのテストでのプログラムの実行結果が通知されます。

この課題では、採点する解答を選択できます。その場合、次の解答のうち成績のよい方に対して得点が与えられます。

• 明示的に選択した解答。
• 最後に審査のために受理された解答。

選択しなかった場合は、次の解答のうち最も成績のよいものが採点されます。

• 得点を確認した解答。
• 最後に審査のために受理された解答。