Num certo instante, chamado instante inicial, os ciclistas que participam numa corrida de estrada encontram-se a distâncias de $x_1,x_2,\ldots,x_n$ metros do ponto de partida ($n$ é o número total de ciclistas). Cada ciclista desloca-se com a sua própria velocidade constante; as velocidades são $v_1,v_2,\ldots,v_n$ metros por segundo. Todos se deslocam no mesmo sentido.

Um repórter que acompanha a competição quer determinar o instante em que a distância entre o ciclista da frente e o último é mínima, para fotografar de um helicóptero todos os participantes da corrida ao mesmo tempo.

Escreve um programa que, dados o número de ciclistas $n$, as suas posições iniciais $x_1,x_2,\ldots,x_n$ e as suas velocidades $v_1,v_2,\ldots,v_n$, calcule um instante $t$ em que a distância $l$ entre o primeiro e o último ciclista seja mínima.

Entrada

A primeira linha do ficheiro de entrada contém um inteiro $n$, o número de ciclistas.

As $n$ linhas seguintes contêm dois inteiros cada uma: $x_i$, a distância desde a partida até ao ciclista $i$ no instante inicial ($0\le x_i\le10^7$), e $v_i$, a sua velocidade ($0\le v_i\le10^7$).

Saída

Escreve dois números reais no ficheiro de saída: $t$, o tempo em segundos decorrido desde o instante inicial até a distância em metros entre o primeiro e o último ser mínima, e $l$, essa distância.

Os números $t$ e $l$ devem ter um erro absoluto ou relativo não superior a $10^{-6}$. Isto significa que, se o número apresentado é $x$ e a resposta correta é $y$, a resposta é considerada correta se $|x-y|/\max\{1,|y|\}$ não exceder $10^{-6}$.

Exemplos

Entrada 1

3
0 40
30 10
40 30

Saída 1

1 30

Entrada 2

5
90 100
100 70
100 70
110 60
120 35

Saída 2

0.5 5.000000000000

Subtarefas

Este problema contém quatro subtarefas. Cada subtarefa é avaliada com o seu próprio grupo de testes. Os pontos de uma subtarefa só são atribuídos se todos os testes desse grupo forem superados.

Subtarefa 1 (20 pontos)

$2\le n\le50$, $0\le x_i\le1000$, $0\le v_i\le1000$. É garantido que existe uma resposta em que $t$ é um inteiro não superior a $1000$.

Subtarefa 2 (20 pontos)

$2\le n\le200$.

Subtarefa 3 (30 pontos)

$2\le n\le2000$.

Subtarefa 4 (30 pontos)

$2\le n\le10^5$.

Retorno da avaliação

Durante a prova, podes solicitar os resultados do teu programa nos testes do júri no máximo 10 vezes. Os pedidos não podem ser feitos com uma frequência superior a uma vez a cada 5 minutos. Para cada teste, é informado o resultado da execução do programa nesse teste.

Neste problema, podes escolher qual solução será avaliada. Nesse caso, a pontuação é atribuída à melhor das seguintes soluções:

• a solução escolhida explicitamente;
• a última solução aceite para avaliação.

Se não for feita uma escolha, será avaliada a melhor das seguintes soluções:

• as soluções cujas pontuações foram consultadas;
• a última solução aceite para avaliação.