Zu einem bestimmten Zeitpunkt, der Anfangszeitpunkt genannt wird, befinden sich die Teilnehmer eines Straßenradrennens in Abständen von $x_1,x_2,\ldots,x_n$ Metern vom Startpunkt ($n$ ist die Gesamtzahl der Radfahrer). Jeder Radfahrer fährt mit seiner eigenen konstanten Geschwindigkeit; die Geschwindigkeiten betragen $v_1,v_2,\ldots,v_n$ Meter pro Sekunde. Alle fahren in dieselbe Richtung.

Ein Reporter, der über den Wettbewerb berichtet, möchte den Zeitpunkt bestimmen, zu dem der Abstand zwischen dem führenden und dem letzten Radfahrer minimal ist, um alle Teilnehmer des Radrennens gleichzeitig aus einem Hubschrauber zu fotografieren.

Schreibe ein Programm, das anhand der Anzahl der Radfahrer $n$, ihrer Anfangspositionen $x_1,x_2,\ldots,x_n$ und ihrer Geschwindigkeiten $v_1,v_2,\ldots,v_n$ einen Zeitpunkt $t$ berechnet, zu dem der Abstand $l$ zwischen dem führenden und dem letzten Radfahrer minimal ist.

Eingabe

Die erste Zeile der Eingabedatei enthält eine ganze Zahl $n$, die Anzahl der Radfahrer.

Die folgenden $n$ Zeilen enthalten jeweils zwei ganze Zahlen: $x_i$, den Abstand des Radfahrers $i$ vom Start zum Anfangszeitpunkt ($0\le x_i\le10^7$), und $v_i$, seine Geschwindigkeit ($0\le v_i\le10^7$).

Ausgabe

Gib zwei reelle Zahlen in die Ausgabedatei aus: $t$, die seit dem Anfangszeitpunkt verstrichene Zeit in Sekunden bis der Abstand in Metern zwischen dem führenden und dem letzten Radfahrer minimal ist, und $l$, diesen Abstand.

Die Zahlen $t$ und $l$ dürfen einen absoluten oder relativen Fehler von höchstens $10^{-6}$ haben. Das bedeutet: Ist die ausgegebene Zahl $x$ und die richtige Antwort $y$, wird die Antwort als richtig gewertet, wenn $|x-y|/\max\{1,|y|\}$ höchstens $10^{-6}$ beträgt.

Beispiele

Eingabe 1

3
0 40
30 10
40 30

Ausgabe 1

1 30

Eingabe 2

5
90 100
100 70
100 70
110 60
120 35

Ausgabe 2

0.5 5.000000000000

Teilaufgaben

Diese Aufgabe umfasst vier Teilaufgaben. Jede Teilaufgabe wird mit einer eigenen Testgruppe bewertet. Punkte werden nur vergeben, wenn alle Tests der jeweiligen Gruppe bestanden werden.

Teilaufgabe 1 (20 Punkte)

$2\le n\le50$, $0\le x_i\le1000$, $0\le v_i\le1000$. Es ist garantiert, dass eine Antwort existiert, bei der $t$ eine ganze Zahl von höchstens $1000$ ist.

Teilaufgabe 2 (20 Punkte)

$2\le n\le200$.

Teilaufgabe 3 (30 Punkte)

$2\le n\le2000$.

Teilaufgabe 4 (30 Punkte)

$2\le n\le10^5$.

Rückmeldung

Während der Runde kannst du höchstens 10-mal die Ergebnisse deines Programms auf den Tests der Jury abfragen. Eine Abfrage darf höchstens einmal alle 5 Minuten erfolgen. Für jeden Test wird das Ergebnis der Programmausführung auf diesem Test mitgeteilt.

Bei dieser Aufgabe kannst du auswählen, welche Lösung bewertet wird. In diesem Fall werden die Punkte für die bessere der folgenden Lösungen vergeben:

• die ausdrücklich ausgewählte Lösung;
• die zuletzt zur Bewertung angenommene Lösung.

Wenn keine Auswahl getroffen wird, wird die beste der folgenden Lösungen bewertet:

• die Lösungen, deren Punktzahlen eingesehen wurden;
• die zuletzt zur Bewertung angenommene Lösung.