Conversa não tão secreta
A polícia desconfia que dois homens que passeiam todos os dias pelo parque são na verdade criminosos. O parque é plano, de formato retangular, e estreitas faixas de grama o dividem em quadrados de mesmo tamanho, formando uma grade de N por M quadrados.
Os dois homens têm um comportamento curioso e suspeito em seu passeio: após encontrarem-se, conversam durante um minuto, andam mudando rapidamente de lugar, passando a ocupar um novo quadrado do parque, conversam mais um minuto, andam novamente (mudando de quadrado), conversam mais um minuto, e assim sucessivamente. A cada minuto escolhem uma direção (Norte, Sul, Leste ou Oeste) e andam até o quadrado imediatamente vizinho na direção escolhida.
Tentando escutar trechos das conversas dos homens, a polícia instalou um pequeno microfone multi-direcional em um dos quadrados do parque. O microfone é capaz de captar conversas realizadas no quadrado onde está instalado e em todos os quadrados imediatamente vizinhos.
Os dois homens sempre iniciam o passeio no quadrado de coordenadas (0,0).
Dadas as coordenadas do microfone e a sequência de movimentos que os dois homens realizaram durante seu passeio no parque, seu programa deve determinar quantos minutos do conversa foram captados pelo microfone.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém dois inteiros N e M que indicam respectivamente o número de linhas e o número de colunas do parque. A segunda linha contém dois inteiros X e Y que indicam a coordenada do microfone em termos de linhas e colunas. A terceira linha contém um inteiro K, indicando o número de quadrados pelos quais os dois homens passearam. A quarta linha contém K inteiros, entre 1, 2, 3 e 4, que indicam a rota tomada pelos dois homens durante o passeio; cada inteiro indica a direção tomada ao final de um minuto de conversa, com 1 representando o Norte, 2 representando o Sul, 3 representando o Leste e 4 representando o Oeste.Saída
Seu programa deve imprimir uma única linha contendo um único inteiro: o número de minutos de conversação captados pelo microfone.
Restrições
- 0 ≤ N ≤ 1 000 000
- 0 ≤ M ≤ 1 000 000
- 1 ≤ K ≤ 10 000
Exemplos
Entrada
10 10 2 2 3 3 3 3 |
Saída
0 |
Entrada
5 5 0 1 3 3 1 3 |
Saída
3 |
Entrada
20 20 3 2 8 1 1 3 3 1 1 2 4 |
Saída
6 |
