Percurso de Bicicleta

image imagem

Dois amigos resolveram realizar uma viagem de bicicleta de Lisboa até Santarém, num único dia. O percurso é constituído por 7 troços:

Lisboa – Santa Iria de Azóia;
Santa Iria de Azóia – Forte da Casa;
Forte da Casa – Vila Franca de Xira;
Vila Franca de Xira – Carregado;
Carregado – Azambuja;
Azambuja – Cartaxo;
Cartaxo – Santarém.

O final de cada troço é um local de controlo.

Os amigos têm de registar os instantes em que partem de Lisboa e em que passam nos locais de controlo. Assuma que, em qualquer um destes locais (partida ou de controlo), os instantes registados pelos dois amigos nunca são iguais. Os amigos também combinaram que só poderiam ultrapassar-se uma única vez em cada troço, ou seja, se o amigo A ultrapassasse o amigo B num dado troço, então B já não poderia ultrapassar A nesse troço.

No final da viagem, os amigos querem saber em que troços do percurso houve ultrapassagens e qual deles ultrapassou o outro, bem como quem chegou primeiro a Santarém.

Tarefa

Escreva um programa que, dados os nomes dos amigos e os instantes registados por eles, indica as ultrapassagens realizadas e quem chegou primeiro a Santarém.

Input

Cada uma das duas primeiras linhas do input tem o nome de um amigo, que é uma sequência não vazia de (no máximo, 50) caracteres. Os dois nomes,

N_{1}

N_{2}

, são distintos.

A terceira linha tem quatro inteiros, $H_{01}$ , $M_{01}$ , $H_{02}$ e $M_{02}$ , que representam os instantes em que os amigos partiram de Lisboa: o amigo $N_{1}$ partiu às $H_{01}$ horas e $M_{01}$ minutos e o amigo $N_{2}$ partiu às $H_{02}$ horas e $M_{02}$ minutos. Cada uma das restantes sete linhas tem quatro inteiros, $H_{i 1}$ , $M_{i 1}$ , $H_{i 2}$ e $M_{i 2}$ , que representam os instantes em que os amigos chegaram ao fim do $i$ -ésimo troço do percurso (com $i = 1, \dots, 7$ ). Assuma que, em cada uma destas oito linhas, os dois instantes especificados são diferentes.

Restrições

	$0 \leq H_{i j} \leq 23$	Horas de partida ou de passagem num local de controlo (para $i = 0, 1, \dots, 7$ e $j = 1, 2$ )
	$0 \leq M_{i j} \leq 59$	Minutos de partida ou de passagem num local de controlo (para $i = 0, 1, \dots, 7$ e $j = 1, 2$ )

Output

O output tem

U + 1

linhas (com

0 \leq U \leq 7

). As primeiras

U

linhas referem-se às ultrapassagens. Há uma linha por cada troço onde ocorreu uma ultrapassagem, que tem a seguinte forma, onde NomeAmigo denota o nome do amigo que ultrapassou e LocalOrigem e LocalDestino representam, respetivamente, as localidades onde o troço começa e termina:

NomeAmigo ULTRAPASSA em LocalOrigem - LocalDestino
As localidades devem ser escritas em maiúsculas e sem acentos: LISBOA, SANTA IRIA DE AZOIA, FORTE DA CASA, VILA FRANCA DE XIRA, CARREGADO, AZAMBUJA, CARTAXO e SANTAREM. Estas linhas devem ser escritas por ordem cronológica (pela ordem dos troços). A última linha contém o nome do amigo que chegou primeiro a Santarém.

Exemplo 1

Input

Maria Santos
Jose Santos
12 50 13 5
14 5 14 10
14 50 14 51
15 40 15 41
16 30 16 41
17 10 17 15
18 5 18 54
20 0 20 10

Output

Maria Santos

Exemplo 2

Input

Jorge S
Joana S
12 50 13 5
14 5 14 20
14 50 14 51
15 40 15 41
16 30 16 41
17 10 17 5
18 5 18 4
20 0 20 10

Output

Joana S ULTRAPASSA em CARREGADO - AZAMBUJA
Jorge S ULTRAPASSA em CARTAXO - SANTAREM
Jorge S

ToPAS'2025