Problema D - Torres

O Rodrigo é um grande fã de xadrez e de programação, mas o jogo de xadrez clássico rapidamente ficou aborrecido para ele, e por isso decidiu começar a divertir-se com as peças que representam uma torre.

Ele descobriu um tabuleiro de N linhas por N colunas contendo T torres lá colocadas. O jogo do Rodrigo tem as seguintes regras:

1. O poder de cada torre é determinado por um inteiro.
2. Uma torre vê todas as posições que estão na sua linha ou na sua coluna, excepto a sua própria posição.
3. Dizemos que uma posição é atacada se um XOR binário (ou exclusivo) dos poderes de todos as torres que vêem essa posição é maior que zero.

Nota que a posição onde está uma torre pode ou não ser atacada.

O Problema

Inicialmente, o Rodrigo colocou as torres de uma determinada maneira no tabuleiro e irá fazer M movimentos. Depois de cada movimento, tens de determinar quantas posições são atacadas.

Num movimento, uma torre pode ser movida para qualquer posição do tabuleiro (e não apenas na mesma linha ou coluna).

Input

A primeira linha de input contém inteiros N, T e M, respetivamente as dimensões o tabuleiro, o número de torres e o número de movimentos a efetuar.

Cada uma das seguintes T linhas contém 3 inteiros L, C e P, que indicam a existência de uma torre com poder P na posição (L,C).

As M linhas seguintes contêm 4 inteiros L₁, C₁, L₂ e C₂, que denotam que a torre da posição (L₁, C₁) foi movimentada para a posição (L₂, C₂).

É garantido que nunca vão estar duas torres na mesma posição, ao mesmo tempo.

Output

M linhas, sendo que a késima linha contém o número total de posições atacadas depois de k movimentos.

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 2 grupos com restrições adicionais diferentes:

Input de Exemplo 1

2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2

Output de Exemplo 1

4
0

Explicação do Exemplo 1

Depois do primeiro movimento, todas as posições do tabuleiro são atacadas. Por exemplo, a posição (1,1) é vista apenas por uma torre, pelo que o total XOR dessa posição é 1.
Depois do segundo movimento, nenhuma posição é atacada. Por exemplo, a posição (1,1) é vista por ambas as torres, pelo que o total XOR dessa posição é 0.

Input de Exemplo 2

2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2

Output de Exemplo 2

4
2

Input de Exemplo 3

3 3 4
1 1 1
2 2 2
2 3 3
2 3 3 3
3 3 3 1
1 1 1 2
3 1 3 2 

Output de Exemplo 3

6
7
7
9