Problema C - Transmissão secreta

Na era da Internet e da globalização, ainda restam alguns segredos que devem ser mantidos. A Organização Naútica Internacional todos os dias partilha mensagens secretas entre as suas sucursais através de uma rede de torres de transmissão.

O mapa onde se desenvolve toda a atividade naútica é representado por uma grelha de L linhas por C colunas. Em cada célula da grelha pode figurar uma torre de transmissão, um obstáculo (como rochas) ou um espaço vazio. A imagem seguinte representa um possível mapa onde L = 5 e C = 5 (as rochas representam obstáculos, as torres representam torres de transmissão e as restantes são células vazias):

Cada torre de transmissão tem um alcance de D unidades, o que significa que consegue enviar uma mensagem a todas as células a uma distância de até D unidades, sendo que medimos a distância em número mínimo de movimentos cardeais (cima, baixo, esquerda e direita) que não atravessam obstáculos que separam duas células. Para o exemplo dado, se D = 3, as células sublinhadas mostram as células ao alcance da torre mais próxima do canto inferior esquerdo:

Quando há uma mensagem para ser transmitida, pretende-se passar essa mensagem a todas as células sem obstáculo (ou seja, as vazias ou com uma torre). Para tal, inicialmente um conjunto de torres é escolhido para transmitir. Quando uma torre transmite uma mensagem, essa mensagem chega a todas as células no seu alcance. Além disso, todas as torres que estiverem no seu alcance recebem a mensagem e transmitem-na também para todas as torres no seu alcance e por aí fora, numa espécie de reação em cadeia (é possível que uma torre transmita uma mensagem a uma outra torre, que por sua vez transmite a outra e por aí fora). Infelizmente, cada torre tem custo de transmissão, que só é cobrado caso essa torre pertença ao conjunto inicial escolhido para transmitir, ou seja, se uma torre receber a mensagem de outra torre, então não é cobrado nenhum custo. A tua tarefa será determinar o conjunto inicial de torres para transmitir com custo mínimo, mas que transmite a mensagem para todas as células sem obstáculo da grelha. Nota que é garantido que para qualquer mapa se escolhermos todas as torres para transmitir cobrimos sempre a grelha completa (ou seja, há sempre uma solução).

Para complicar ainda mais a situação, os custos de cada torre não são fixos, como há sempre peças a avariar e trabalhadores a mudar, os custos vão variando ao longo do tempo. Serão indicadas Q mudanças de custo, em cada mudança o custo de uma única torre poderá subir ou descer. O custo inicial de todas as torres (antes de qualquer mudança) é 1 e o custo de cada torre será sempre positivo, mesmo depois de cada mudança. A tua tarefa é determinar o custo mínimo de transmissão após cada mudança.

Para simplificar o input, as torres são numeradas de 1 a N (onde N é o número de torres, para o exemplo anterior, N = 4). Isto é feito de cima para baixo e da esquerda para a direita na grelha. Por exemplo, para o mapa que vimos anteriormente, a numeração das torres é a seguinte:

Antes de qualquer mudança, o custo mínimo de transmissão é 2, por exemplo, escolhendo as torres 1 e 2 (ambas com custo 1 inicial), sendo que a torre 1 atinge a torre 3 e a torre 2 atinge a torre 4. Após cada modificação temos os seguintes custos:

• Se o custo da torre 1 for modificado para 1 nada se altera, visto que já era o seu custo original, ou seja, o custo mínimo é 2.
• Se o custo da torre 1 for modificado para 5, o custo mínimo continua a ser 2, mas desta vez escolhendo as torres 2 e 3 (ambas com custo 1 inicial).
• Se o custo da torre 2 passar a ser 3, o custo mínimo mantém-se em 2, mas desta vez escolhendo as torres 3 e 4 (ambas com custo 1 inicial).
• Finalmente se o custo da torre 4 passar a ser 7, então o custo mínimo passa a ser 4, escolhendo as torres 2 e 3 (a torre 2 com custo 3 e a torre 3 com custo 1).

O Problema

Dada uma grelha de L linhas por C colunas contendo células vazias, obstáculos e torres de transmissão, assim como Q mudanças de custo de torres, determinar, para o estado da grelha após cada mudança, o custo mínimo de transmissão para a grelha completa.

Input

Na primeira linha vêm três inteiros, L que representa o número de linhas, C que representa o número de colunas e D que representa alcance de cada torre.

Seguem-se L linhas, cada uma com C carateres representando a grelha onde: '.' representam espaços vazios; '#' representam obstáculos; 'T' representam torres.

Segue-se uma linha com um único inteiro, Q, que representa o número de mudanças de custo.

Seguem-se Q linhas, cada uma com dois inteiros T_i e Q_i, onde T_i representa a torre cujo custo muda na i-ésima mudança e Q_i o novo custo dessa torre.

Output

O output deve conter Q linhas, onde a i-ésima linha representa o custo mínimo do conjunto de torres a transmitir após a i-ésima mudança de custo.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input do Exemplo 1

5 5 3
.#...
T#.T.
.#...
T...T
.....
4
1 1
1 5
2 3
4 7

Output do Exemplo 1

2
2
2
4
    

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado.

Input do Exemplo 2

3 4 2
T..T
....
T..T
5
1 5
4 5
2 5
3 5
1 1

Output do Exemplo 2

2
2
6
10
6

Input do Exemplo 3

10 10 5
.#.T...#.#
T.T##..T..
..####T..T
...##.....
..T..#.##.
.#.#T#.#..
..#.#...##
.#.......#
...#.#.#T.
....T#...#
3
10 2
9 3
10 3

Output do Exemplo 3

4
6
7