SPOJ Brasil

Dois professores (PA e PB){A saber: PA é o prof. Castellone, e PB é o prof. Anthov, ambos do DINF} combinaram de encontrar-se no Centro Politécnico (CP) às 15h00 numa quarta-feira. Como os professores são grandes estudiosos de movimentos retilíneos uniformes, pensaram em aplicar um de seus estudos mais recentes. Os dois professores dividiram o CP em um grande quadriculado. A cada passo, cada professor escolhe uma direção (Norte, Sul, Leste ou Oeste) e anda até o quadrado imediatamente vizinho na direção escolhida.

O quadriculado do CP é um plano cartesiano com origem em (1,1) como sendo o limite inferior esquerdo e as direções Norte e Sul andam no eixo Y, e as direções Leste e Oeste no eixo X. As direções Norte e Leste incrementam a posição de seus respectivos eixos e Sul e Oeste fazem o oposto.

Dada uma sequência de passos, você deve dizer se os professores se encontraram em algum momento, i.e, se eles ficaram no mesmo quadrado ao mesmo tempo, se algum professor saiu do CP ou se eles não se encontraram.

Entrada

A primeira linha da entrada contém dois inteiros N e M que indicam respectivamente o número de colunas e o número de linhas do CP (1 <= N, M <= 10⁵). A segunda linha contém um inteiro P (0 <= P <= 1000) que indica quantos movimentos cada professor fez. Depois são apresentadas P linhas contendo dois números inteiros A e B, indicando a direção tomada pelos professores PA e PB, respectivamente, naquele passo. Os inteiros A e B podem assumir os seguintes valores: 1 (Norte), 2 (Sul), 3 (Leste) e 4 (Oeste). O professor PA inicia seu trajeto sempre na posição (1,1) e o professor PB na posição (N,M).

Saída

Seu programa deve imprimir:

• Caso os professores tenham se encontrado: as coordenadas do encontro e o passo em que ocorreu.
• Caso o(s) professor(es) tenha(m) saído do CP: as coordenadas em que saíram e o passo em que ocorreu. Se ambos professores saíram no mesmo passo imprima apenas a informação sobre o professor PA.
• Caso nenhuma das anteriores ocorra, imprimir: “Nao se encontraram”.

Verifique os exemplos para entender melhor o formato da saída.

Exemplos

Entrada:
5 5
4
3 2
3 2
3 2
3 4

Saída:
Nao se encontraram

Entrada:
5 5
4
3 2
3 2
3 2
3 2

Saída:
Encontraram-se na posicao (5,1) no passo 4

Entrada:
5 5
4
1 2
1 2
4 1
1 4

Saída:
PA saiu na posicao (0,3) no passo 3