Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RINGMG - Ring of Kerry

Ring of Kerry é um dos passeios turísticos famosos na Irlanda. Partindo de Killarney, consiste em um trajeto circular de quase 180 km pelo condado de Kerry, passando por lagos, parques, fortes e castelos. Ônibus de excursão são obrigados a percorrer o trajeto no sentido anti-horário, para evitar que se cruzem durante o percurso, já que em alguns pontos a estrada é bastante estreita. Os automóveis, por outro lado, são orientados a fazer o trajeto no sentido horário, para que não fiquem atrás de longas fileiras de ônibus.

Nesta questão você também vai trabalhar com uma pista circular, mas diferentemente do Ring of Kerry, o trajeto pode ser iniciado em qualquer local, e ser percorrido em qualquer direção. No trajeto existem n postos de abastecimento, e o total de combustível disponível nesses postos é suficiente (exatamente) para uma volta na pista. Em qual posto um automóvel, com tanque inicialmente vazio, deve começar o trajeto para conseguir dar a volta completa (abastecendo ao longo do caminho)?

Por exemplo, considere a seguinte pista, com 5 postos de abastecimento, numerados no sentido horário de 1 a 5. Para cada posto i é mostrada a quantidade Pi de combustível disponível para abastecimento. Para cada trecho entre os postos é mostrada a quantidade de litros de combustível necessária para percorrer o trecho.

Se o carro iniciar o trajeto no posto 1 ele consegue terminar o percurso no sentido horário. Se ele iniciar o trajeto no posto 4, consegue terminar o percurso no sentido anti-horário.

Entretanto, se ele iniciar o trajeto em qualquer outro posto, não conseguirá terminar o percurso, independentemente do sentido em que percorrer a pista. Por exemplo, se iniciar o trajeto no posto 2, ficará sem combustível quando for percorrer o trecho entre os postos 5 e 1 (chegará ao posto 5 com tanque vazio, abastecerá 3 litros, e assim não terá os 4 litros necessários para chegar ao posto 1).

Dado o número de postos, o combustível disponível em cada um, e a quantidade de combustível necessária para chegar ao posto seguinte, determinar em qual posto um veículo com tanque inicialmente vazio deve começar o trajeto para conseguir percorrer toda a pista no sentido horário, e em qual começar para conseguir percorrê-la no sentido anti-horário.

Observações

Considere que o tanque do veículo tem capacidade ilimitada, ou seja, sempre que chegar em um posto, ele abastece o tanque com toda a quantidade disponível no posto.

Entrada

A entrada contém vários casos de teste. Cada caso de teste é dado em três linhas.

A primeira linha de cada caso de teste contém um inteiro N que indica a quantidade de postos de abastecimento ao longo da pista (1 ≤ N ≤ 1.000). Em seguida, há uma linha contendo N valores Pi, que indicam a quantidade de combustível disponível no i-ésimo posto (0 ≤ Pi ≤ 50). Em seguida, há uma linha contendo N valores Ci, que indicam a quantidade de combustível necessária para ir do posto i até o posto i+1, que é o posto seguinte no seguinte horário (1 ≤ Ci ≤ 100). Como a pista é circular, e os postos são numerados sequencialmente de 1 a N no sentido horário, o valor CN indica a quantidade necessária para ir do posto N ao posto 1.

Considere que as distâncias são simétricas, de forma que a quantidade necessária para ir de um posto A a um posto adjacente B é a mesma necessária para ir de B para A.

A entrada termina quando N = 0

Saída

Para cada caso de teste escreva uma linha contendo dois valores: o número do posto onde se deve iniciar o trajeto no sentido horário e o número do posto onde se deve iniciar o trajeto no sentido anti-horário.

Para cada sentido, se não for possível percorrer a pista escreva -1, e se houver mais de um posto a partir do qual é possível percorrê-la, escreva o de menor índice entre eles.

Exemplos

Entrada:
5
11 10 7 9 3
10 6 8 12 4
4
10 10 10 10
10 10 10 10
3
1 20 5
22 3 1
0

Saída:
1 4
1 1
2 1

O primeiro caso de teste corresponde ao exemplo dado na figura do enunciado.


Adicionado por:Wanderley Guimarăes
Data:2014-05-09
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Maratona Mineira 2013

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.