Palavras Cruzadas

Você já deve ter tentado completar um jogo de palavras cruzadas. Nesse jogo, o jogador deve descobrir um conjunto de palavras através de dicas fornecidas juntamente com um retângulo dividido em quadrados de mesmo tamanho, sendo a maioria quadrados em branco e alguns quadrados pretos. Cada linha e cada coluna formada pelos quadrados em branco deve ser preenchida por uma palavra, com uma letra em cada quadrado em branco. As palavras das linhas são chamadas de palavras horizontais, as palavras das colunas são chamadas palavras verticais. As palavras horizontais cruzam com as palavras verticais em uma letra comum às duas palavras, vindo daí o nome do jogo.

Nesta tarefa, dadas uma palavra horizontal e uma palavra vertical, você deve encontrar a melhor letra de cruzamento entre elas, que é definida como a letra que produz

1. o cruzamento mais à direita possível na palavra horizontal;
2. se há mais de uma possibilidade de cruzamento com a regra (1), a melhor letra de cruzamento é definida como a que produz o cruzamento mais abaixo possível na palavra vertical.

A figura abaixo ilustra alguns exemplos. Entre parênteses estão os índices da melhor letra de cruzamento. O índice de uma letra é a posição que ela ocupa na palavra, iniciando com 1 (primeira letra).

Entrada

A primeira linha da entrada contém a palavra horizontal. A segunda linha da entrada contém a palavra vertical.

Saída

Seu programa deve produzir uma única linha, contendo apenas dois inteiros descrevendo a melhor letra de cruzamento. O primeiro número deve ser o índice da letra de cruzamento na palavra horizontal, o segundo número deve ser o índice da letra de cruzamento na palavra vertical. Se não há letra de cruzamento possível, os dois inteiros devem ser iguais a $-1$.

Restrições

• As palavras são compostas por letras maiúsculas não acentuadas, com comprimento de pelo menos uma letra e de no máximo $1\ 000$ letras.

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo $20$ pontos há exatamente uma possibilidade de cruzamento possível.
• Para um conjunto de casos de testes valendo $80$ pontos adicionais não há restrições adicionais.

Exemplos

Exemplo de entrada 1

PATO
PELE

Exemplo de saída 1

1 1

Exemplo de entrada 2

ANJO
MENTORA

Exemplo de saída 2

4 5

Exemplo de entrada 3

MENTORA
ANJO

Exemplo de saída 3

7 1

Exemplo de entrada 4

URUBU
POLIVALENTE

Exemplo de saída 4

-1 -1