XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: conversa.x, onde x deve ser c, cpp, java, js ou py

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
Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação