Trilhas

Nos finais de semana, Paulo faz longas caminhadas pelas bonitas trilhas que atravessam as matas vizinhas à sua cidade. Recentemente Paulo adquiriu um aparelho de GPS e com ele mapeou as mais belas trilhas da região. Paulo programou o GPS para armazenar, a intervalos regulares, a altitude do ponto corrente durante o trajeto. Assim, após percorrer as trilhas com o seu GPS, Paulo tem informações que permitem por exemplo produzir gráficos como os abaixo:

Paulo tem uma nova namorada, e quer convencê-la a passear junto com ele pelas trilhas. Para o primeiro passeio juntos, Paulo quer escolher uma trilha “fácil”. Segundo o seu critério, a trilha mais fácil é a que, em um dos sentidos do percurso, exige o menor esforço de subida. O esforço exigido em um trecho de subida é proporcional ao desnível do trecho.

Tarefa

Dadas as informações colhidas por Paulo sobre distâncias e altitudes de um conjunto de trilhas, você deve escrever um programa que determine qual é a trilha que exige o menor esforço de subida.

Entrada

A primeira linha da entrada contém um número inteiro $N$ que indica o número de trilhas. Cada uma das $N$ linhas seguintes contém a descrição de uma trilha ($1 \leq N \leq 100$). As trilhas são identificadas por números de $1$ a $N$. A ordem em que as trilhas aparecem na entrada determina os seus identificadores (a primeira trilha é a de número $1$, a segunda a de número $2$, a última a de número $N$). A descrição de uma trilha inicia com um número inteiro $M$ que indica a quantidade de pontos de medição da trilha ($2 \leq M \leq 1000$), seguido de $M$ números inteiros $H_i$ representando a altura dos pontos da trilha (medidos a intervalos regulares e iguais para todas as linhas). Paulo pode percorrer a trilha em qualquer sentido (ou seja, partindo do ponto de altitude $H_1$ em direção ao ponto de altitude $H_M$, ou partindo do ponto de altitude $H_M$ em direção ao ponto de altitude $H_1$).

Saída

Seu programa deve produzir uma única linha na saída, contendo um número inteiro representando o identificador da melhor trilha, conforme determinado pelo seu programa. Em caso de empate entre duas ou mais trilhas, imprima a de menor identificador.

Exemplo de Entrada 1

5
4 498 500 498 498
10 60 60 70 70 70 70 80 90 90 100
5 200 190 180 170 160
2 1000 900
4 20 20 20 20

Exemplo de Saída 1

2

Exemplo de Entrada 2

3
5 600 601 600 601 600
4 500 499 500 499
4 300 300 302 300

Exemplo de Saída 2

2