Dança de Formatura

A escola de educação básica do seu bairro está organizando uma festa de formatura para os graduandos deste ano. Para isso, eles pediram que a OBI (Organização de Brincadeiras Infantis) desenvolva uma dança que os alunos possam apresentar aos pais durante a formatura.

A dança da OBI é dançada em uma pista quadriculada com $N$ linhas e $M$ colunas, sempre com exatamente um aluno em cada quadrado do pista. Os alunos são numerados de $1$ a $N \times M$ de acordo com a sua posição inicial na pista em ordem crescente de linha e coluna, nesta ordem, a partir do quadrado $(1, 1)$. O exemplo abaixo, para $N = 4$ e $M = 3$, indica o número do aluno em cada quadrado da pista no início da dança; o aluno de número $7$, por exemplo, inicia no quadrado $(3, 1)$.

A cada passo da dança, o professor dá aos alunos uma das duas ordens abaixo:

• “L $a$ $b$” (onde $a$ e $b$ são inteiros distintos), ordenando que os alunos da $a$-ésima linha troquem de linha com os alunos da $b$-ésima linha, mantendo a coluna de cada um – ou seja, o aluno na célula $(a, 1)$ troca com o aluno na célula $(b, 1)$, $(a, 2)$ troca com $(b, 2)$ e assim por diante.
• “C $a$ $b$” (onde a e b são inteiros distintos), ordenando que os alunos da $a$-ésima coluna troquem de coluna com os alunos da $b$-ésima coluna, mantendo a linha de cada um – ou seja, o aluno na célula $(1, a)$ troca com o aluno na célula $(1, b)$, $(2, a)$ troca com $(2, b)$ e assim por diante.

A figura abaixo ilustra o progresso da dança para $N = 4$ e $M = 3$ com os três primeiros passos sendo “C $1$ $3$”, “L $1$ $4$” e “C $3$ $2$”, nesta ordem.

A escola gostou muito da dança inventada pela OBI e deseja usá-la na formatura. Porém, os pais não querem perder seus filhos de vista e pediram sua ajuda para saber quais serão as posições de seus filhos ao término da dança.

Sua tarefa é: dadas as dimensões $N$ e $M$ da pista de dança, a quantidade $P$ de passos da dança e a ordem dada pelo professor a cada passo, determine qual aluno estará em cada quadrado da pista ao fim da dança.

Entrada

A primeira linha da entrada é composta por três inteiros $N$, $M$ e $P$ indicando, respectivamente, o número de linhas da pista de dança, o número de colunas da pista de dança, e o número de passos da dança.

As próximas $P$ linhas descrevem as ordens dadas pelo professor. A $i$-ésima dessas linhas contém uma letra maiúscula $O_i$, que pode ser ‘L’ ou ‘C’, seguida de dois inteiros distintos $A_i$ e $B_i$.

• Se $O_i =$ ‘L’, o professor ordenou a troca das linhas $A_i$ e $B_i$.
• Se $O_i =$ ‘C’, o professor ordenou a troca das colunas $A_i$ e $B_i$.

Saída

Seu programa deverá imprimir $N$ linhas, cada uma contendo $M$ inteiros. O $j$-ésimo inteiro da $i$-ésima linha deve ser o número do aluno que terminará a dança na $i$-ésima linha e $j$-ésima coluna da pista.

Restrições

• $1 \leq N \leq 1\ 000\ 000$
• $1 \leq M \leq 1\ 000\ 000$
• $1 < N \times M \leq 1\ 000\ 000$
• $1 \leq P \leq 500\ 000$
• $O_i =$ ‘L’ ou $O_i =$ ‘C’
• Se $O_i =$ ‘L’, $1 \leq A_i, B_i \leq N$
• Se $O_i =$ ‘C’, $1 \leq A_i, B_i \leq M$
• $A_i \neq B_i$

Atenção: Observe que não é possível declarar $1\ 000\ 000 \times 1\ 000\ 000$ inteiros (com matriz, vetor etc.) sem estourar o limite de memória (isto causaria erros no programa pois tentaria usar milhares de GB de memória). Preste atenção ao limite $N \times M \leq 1\ 000\ 000$, que garante que a pista de dança sempre terá no máximo $1\ 000\ 000$ alunos.

Informações sobre a pontuação

A tarefa vale $100$ pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:

• Subtarefa 1 (0 pontos): Esta subtarefa é composta apenas pelos exemplos mostrados abaixo. Ela não vale pontos, serve apenas para que você verifique se o seu programa imprime o resultado correto para os exemplos.
• Subtarefa 2 (20 pontos):
  • $N =1$
  • $M \leq 1\ 000$
  • $P \leq 1\ 000$
• Subtarefa 3 (20 pontos):
  • $N \leq 1\ 000$
  • $M \leq 1\ 000$
  • $P \leq 1\ 000$
• Subtarefa 4 (31 pontos):
  • $M = 2$ (Veja o exemplo 3.)
• Subtarefa 5 (29 pontos): Sem restrições adicionais.

Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Exemplo de entrada 1

4 3 3
C 1 3
L 1 4
C 3 2

Exemplo de saída 1

12 10 11
6 4 5
9 7 8
3 1 2

Exemplo de entrada 2

1 6 4
C 2 5
C 1 2
C 4 3
C 1 2

Exemplo de saída 2

1 5 4 3 2 6

Exemplo de entrada 3

5 2 6
C 1 2
L 1 3
L 1 4
C 2 1
L 5 3
C 2 1

Exemplo de saída 3

8 7
4 3
10 9
6 5
2 1