SPOJ Brasil

Autor: Raphael Ribas

A TV da vovó Filomena é muito antiga e sua imagem fica desajustada com muita frequência. No passado ela pediu a sua ajuda para escrever um programa que ajudasse ela a ajustar a imagem da TV. No entanto o programa não ajudava muito porque a vovó Filomena achou a interface de linha de comando muito mais difícil do que ajustar a imagem por ela mesma.

Por fim, vovó Filomena resolveu comprar uma TV nova. Ela escolheu uma TV super avançada com imagens em 3D. No entanto, a nova TV possui novas formas de desajustar a imagem das quais a TV antiga não era capaz, incluindo rotações nas 3 dimensões. Desiludida, ela pediu mais uma vez a sua ajuda para fazer um programa que auxiliasse ela a ajustar a imagem da TV. Felizmente, a vovó Filomena odiou usar os óculos 3D, e estão guardados na gaveta desde a compra da TV. Então você só precisa se preocupar com ajustes em 2 dimensões.

A imagem da TV é representada por N linhas. Cada linha possui N números. Cada número representa a cor da imagem da TV naquela linha e coluna. Os ajustes que a TV pode fazer são:

• Rotação de 90o no sentido horário ou anti-horário,
• Translação em qualquer uma das quatro direções, e
• Espelho vertical ou horizontal.

Sua tarefa é escrever um programa que, dado a imagem da TV e uma sequência de ajustes, determine a imagem final.

Entrada

A entrada é composta por diversas instâncias. A primeira linha de cada instância contém dois inteiro, N e K. As N linhas seguintes contém N números cada. Esses números constituem a imagem inicial da TV. As próximas K linhas contém, cada uma, uma operação a ser realizada na imagem da TV, que podem ser:

• rot 90 - Rotação de 90o no sentido horário,
• rot -90 - Rotação de 90o no sentido anti-horário,
• move direita - Translação de 1 coluna para a direita,
• move esquerda - Translação de 1 coluna para a direita,
• move cima - Translação de 1 linha para cima,
• move baixo - Translação de 1 linha para baixo,
• espelho vertical - Espelho sobre o eixo vertical,
• espelho horizontal - Espelho sobre o eixo horizontal,

Saída

Para cada instância, imprima N linhas, cada uma com N números, com a imagem final da TV, seguido por uma linha em branco.

Restrições

• 1 ≤ N ≤ 1.000
• 1 ≤ K ≤ 1.000.000

Exemplos

Entrada:
3 1
1 2 3
4 5 6
7 8 9
rot 90
3 1
1 2 3
4 5 6
7 8 9
move direita
3 1
1 2 3
4 5 6
7 8 9
espelho vertical
3 7
1 2 3
4 5 6
7 8 9
rot 90
move direita
rot -90
move cima
espelho vertical
move cima
espelho horizontal

Saída:
7 4 1
8 5 2
9 6 3

3 1 2
6 4 5
9 7 8

3 2 1
6 5 4
9 8 7

9 8 7
6 5 4
3 2 1