Melhor Time

Uma discussão recorrente dentre os torcedores é a seguinte: qual é o melhor dentre dois times? Como cada torcedor tem seu próprio critério (que invariavelmente beneficia o seu time…), não é possível chegar a uma conclusão.

As narrações esportivas, antes do início das partidas de futebol, costumam dar uma estatística interessante, que pode dar um panorama da comparação entre dois times em um espaço de tempo determinado: o confronto direto. Neste indicador, é escolhido um intervalo de $N$ partidas consecutivas disputadas entre dois times (na maior parte das vezes, todas as partidas já disputadas entre os dois times) e totaliza-se então os número de vitórias de cada time e o número de empates. Pode-se afirmar que um time venceu o confronto direto naquele intervalo se o time obteve mais vitórias do que seu adversário. Pode ser que, em um determinado intervalo de jogos, não exista um vencedor do confronto direto.

Por exemplo, considere que estes fosse os resultados das últimas 10 partidas disputadas entre o Gama e o Brasiliense:

1. Gama 2 x 1 Brasiliense
2. Gama 1 x 1 Brasiliense
3. Gama 0 x 0 Brasiliense
4. Gama 1 x 4 Brasiliense
5. Gama 1 x 1 Brasiliense
6. Gama 0 x 0 Brasiliense
7. Gama 0 x 0 Brasiliense
8. Gama 0 x 0 Brasiliense
9. Gama 2 x 0 Brasiliense
10. Gama 0 x 1 Brasiliense

Embora não exista um vencedor se considerado o intervalo $[1,10]$ de todas as 10 partidas, o Gama foi o vencedor do confronto no intervalo $[1, 9]$ e o Brasiliense venceu no intervalo $[2, 8]$. Observe que nos intervalos $[1, 8]$ e $[2, 3]$ não houveram vencedores no confronto direto.

Dada uma lista de $N$ confrontos entre os times $A$ e $B$, determine o tamanho do maior intervalo $[m, n]$ de partidas consecutivas tal que, para qualquer $p\in[m,n]$, o time escolhido foi o vencedor do confronto direto no intervalo $[m, p]$.

Entrada

A primeira linha da entrada contém os nomes das equipes $A$ e $B$, separados por um espaço em branco. O nome de uma equipe é uma string de, no máximo, 50 caracteres alfabéticos.

A segunda linha da entrada contém o número $N$ ($1 \leq N \leq 2\times 10^5)$ de jogos consecutivos entre os dois times.

As $N$ linhas seguintes contém, cada uma, o placar do jogo, na forma “$a$ x $b$”, ($0 \leq a, b\leq 20)$, onde $a, b$ representam o número de gols marcados pelas equipes $A$ e $B$, respectivamente.

Saída

Imprima, em uma linha, a mensagem “$A$ x $B$: $I_A$ jogo(s)”, onde $I_A$ é o tamanho do maior intervalo $[m_A, n_A]$ tal que o time $A$ é o vencedor do confronto direto em qualquer intervalo $[m, p_A]$, com $p_a\in[m_A, n_A]$.

De forma análoga imprima, na segunda linha, a mensagem “$B$ x $A$: $I_B$ jogo(s)”.

Exemplo de entrada 1

Gama Brasiliense
10
2 x 1
1 x 1
0 x 0
1 x 4
1 x 1
0 x 0
0 x 0
0 x 0
2 x 0
0 x 1

Exemplo de saída 1

Gama x Brasiliense: 3 jogo(s)
Brasiliense x Gama: 5 jogo(s)

Explicação do exemplo 1: No primeiro caso, o Gama é vencedor o confronto direto nos intervalos $[1, 1], [1, 2], [1, 3], [9, 10]$ e $[10, 10]$, de modo que $[1,3]$ é o maior intervalo com a propriedade descrita. Já o Brasiliense é o vencedor do confronto direto em qualquer prefixo do intervalo $[4, 8]$.

Exemplo de entrada 2

Fluminense Flamengo
5
1 x 0
2 x 3
1 x 2
1 x 1
0 x 1

Exemplo de saída 2

Fluminense x Flamengo: 1 jogo(s)
Flamengo x Fluminense: 4 jogo(s)

Exemplo de entrada 3

Atletico Cruzeiro
3
0 x 1
1 x 0
2 x 2

Exemplo de saída 3

Atletico x Cruzeiro: 2 jogo(s)
Cruzeiro x Atletico: 1 jogo(s)

Exemplo de entrada 4

Gremio Internacional
3
2 x 1
3 x 1
1 x 2

Exemplo de saída 4

Gremio x Internacional: 3 jogo(s)
Internacional x Gremio: 1 jogo(s)