SPOJ Brasil

Pedro e Paulo gostam muito de jogar batalha naval; apesar de serem grandes amigos, Pedro desconfia que Paulo não esteja jogando honestamente. Para tirar essa dúvida, Pedro decidiu usar um programa de computador para verificar o resultado do jogo, mas Pedro não sabe programar e por isso pediu a sua ajuda.

O jogo de batalha naval é jogado em um tabuleiro retangular com N linhas e M colunas. Cada posição deste tabuleiro é um quadrado que pode conter água ou uma parte de um navio. Dizemos que dois quadrados são vizinhos se estes possuem um lado em comum. Se duas partes de navio estão em posições vizinhas, então essas duas partes pertencem ao mesmo navio. A regra do jogo proíbe que os quadrados de duas partes de navios distintos tenham um canto em comum (em outras palavras, que quadrados de duas partes de navios distintos compartilhem um vértice).

Cada disparo que um jogador faz deve ser feito em um dos quadrados do tabuleiro do outro jogador. Um jogador informa ao outro a coluna e a linha do quadrado alvo do disparo. Para que um navio seja destruído, o jogador deve acertar todas as partes deste navio. O jogador não pode atirar no mesmo lugar mais de uma vez

Tarefa

Escreva um programa que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determina o número de navios do outro jogador que foram destruídos.

Entrada

A primeira linha da entrada contém números dois inteiros N e M (1 ≤ N ≤ 100 e M ≤ 100) representando respectivamente o número de linhas e de colunas do tabuleiro. As N seguintes linhas correspondem ao tabuleiro do jogo. Cada uma dessas linhas contém M caracteres. Cada caractere indica o conteúdo da posição correspondente no tabuleiro. Se esse caractere for '.', essa posição contém água; se for '#', essa posição contém uma parte de um navio. A próxima linha contém um número K que é o número de disparos feitos pelo jogador (1 ≤ K ≤ N × M). As próximas K linhas indicam os disparos feitos pelo jogador. Cada linha contém dois inteiros L e C, indicando a linha e a coluna do disparo feito pelo outro jogador (1 ≤ L ≤ N e 1 ≤ C ≤ M).

Saída

Seu programa deve imprimir uma única linha contendo um único número inteiro, o número de navios destruído.

Exemplo

Entrada
5 5
..#.#
#....
 ...#.
 #....
 ...#.
5
1 3
1 4
1 5
2 1
3 4

Saída
4

Entrada
5 5
..###
.....
#####
.....
#.##.
5
5 1
5 2
1 3
1 4
1 5

Saída
2

Entrada
7 7
.#....#
###..##
.#....#
....#.#
.#..#.#
.####.#
.......
8
1 1
1 2
2 1
2 2
2 3
3 2
5 2
6 2

Saída
1