Encontro Politécnico

Dois professores (PA e PB)¹ 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 \leq N, M \leq 10^5$). A segunda linha contém um inteiro P ($0 \leq P \leq 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

Exemplo de entrada

5 5
4
3 2
3 2
3 2
3 4

Saída para o exemplo de entrada acima

Nao se encontraram

Exemplo de entrada

5 5
4
3 2
3 2
3 2
3 2

Saída para o exemplo de entrada acima

Encontraram-se na posicao (5,1) no passo 4

Exemplo de entrada

5 5
4
1 2
1 2
4 1
1 4

Saída para o exemplo de entrada acima

PA saiu na posicao (0,3) no passo 3