Numa galáxia longínqua, existe um estranho planeta rodeado por 4 luas de cor azulada. O planeta
é habitado por seres com uma inteligência muito acima do nível terrestre. Estes habitantes apresentam uma característica muito marcante: eles idolatram completamente
linhas diagonais, considerando-as quase como uma entidade divina! Daí que o seu planeta seja conhecido como Planeta Diagonal.
Os habitantes desse planeta habituam em cubos tridimensionais, sendo que cada habitação ocupa uma porção igual do cubo, conhecida como quadrícula. Nota que cada quadrícula do cubo pode ser identificada por 3 coordenadas, (X,Y,Z) como demonstrado na figura a seguir:
Como identificar uma quadrícula usando um sistema de 3 coordenadas (X, Y e Z começam sempre em 1)
Preguiçosos e inteligentes como são, decidiram que cada quadrícula podia ser identificada apenas por um número, de modo a que a morada de um amigo pudesse ser mais facilmente decorada (por exemplo, o Prof. Curvilíneo, um dos cientistas mais reputado do Planeta Diagonal, mora no cubo habitacional XPTO-22, quadrícula 12). Mas como mapear então as 3 coordenadas num único número? Claro está, como não podia deixar de ser, neste mapeamento foram usadas... linhas diagonais! Para obter a numeração, o cubo é percorrido começando na quadrícula (1,1,1) do seguinte modo:
Como uma face do cubo é percorrida
Quando se "termina" de numerar a face com Z=1, passa-se para a casa imediatamente "atrás", ou seja, a casa com o Z a seguir, mas com o X e Y iguais, tal como exemplificado na figura seguinte:
Um exemplo completo de numeração para um cubo habitacional de dimensão 3x3x3
Nota que com Z=2 é feito precisamente o percurso inverso de Z=1. Já em Z=3 volta a fazer-se o mesmo percurso e se a dimensão do cubo fosse maior, continuaria assim alternadamente. A título de exemplo, como podes ver na figura, num cubo de dimensão 3x3x3, o ponto de coordenadas (1,2,3) corresponde ao número 21, e o número 7 corresponde a (3,2,1).
Este sistema de numeração é conhecido como representação diagonal e passou a ser padrão em todo o planeta. Para os seus habitantes, esta representação é completamente intuitiva. Mas para um simples terrestre como tu... é completamente estranha! Como tens alguns amigos cientistas no Planeta Diagonal, e queres conseguir visitá-los sem te perderes nos cubos habitacionais, resolveste criar um programa que te ajude.
A tua tarefa é escrever um programa que dado um cubo habitacional de uma determinada dimensão, consiga converter entre o sistema de coordenadas tridimensional e a sua respectiva representação com apenas um número do modo atrás descrito. Isto é, se receberes uma coordenada 3D (X,Y,Z) deves devolver o número a que corresponde essa quadrícula na sua representação diagonal. Caso recebas um número, deves devolver quais as coordenadas 3D a que corresponde esse mesmo número, interpretando-o como sendo escrito na representação diagonal.
Na primeira linha aparece um número inteiro N, indicando a dimensão do cubo habitacional a considerar (1 <= N <= 30 000), ou seja, que pretendemos trabalhar sobre um cubo de dimensões NxNxN. Segue-se uma linha contendo um único caracter, 'C' ou 'N', indicando que os números que se seguem representam respectivamente uma coordenada 3D ou um número na representação diagonal.
Depois vem um número inteiro C, indicando o número de casos a considerar (1 <= C <= 30 000). Finalmente vêm exactamente C linhas, cada uma contendo:
Nota que nos casos de teste é garantido que 1 <= X
A primeira linha de output deve conter "NxNxN". Devem seguir-se exactamente por C linhas, uma para cada caso. A linha para o caso i deve conter:
3 N 5 1 2 3 9 10
3x3x3 1 corresponde a (1,1,1) 2 corresponde a (2,1,1) 3 corresponde a (1,2,1) 9 corresponde a (3,3,1) 10 corresponde a (3,3,2)
4 C 3 1 1 1 4 1 1 1 4 1
4x4x4 (1,1,1) corresponde a 1 (4,1,1) corresponde a 7 (1,4,1) corresponde a 10