Encontro Politécnico

Dois professores (PA e PB)1 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)(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 NN e MM que indicam respectivamente o número de colunas e o número de linhas do CP (1N,M1051 \leq N, M \leq 10^5). A segunda linha contém um inteiro P (0P10000 \leq P \leq 1000) que indica quantos movimentos cada professor fez. Depois são apresentadas PP linhas contendo dois números inteiros AA e BB, indicando a direção tomada pelos professores PAPA e PBPB, respectivamente, naquele passo. Os inteiros AA e BB podem assumir os seguintes valores: 11 (Norte), 22 (Sul), 33 (Leste) e 44 (Oeste). O professor PAPA inicia seu trajeto sempre na posição (1,1)(1,1) e o professor PBPB na posição (N,M)(N,M).

Saída

Seu programa deve imprimir:

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

  1. A saber: PA é o prof. Castellone, e PB é o prof. Anthov, ambos do DINF↩︎