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.
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 (1≤N,M≤1051 \leq N, M \leq 10^5). A segunda linha contém um inteiro P (0≤P≤10000 \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).
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.