Colores

Autor: Javier Eduardo Ojeda Jorge

Melchor ha sido contratado por el virrey como pintor oficial del virreinato, frecuentemente el Virrey solicita a Melchor pintar muchos cuadros, como Melchor es un habilidoso y eficiente pintor esta tarea no le resulta complicada, sin embargo al virrey le gustan solo colores de Mersenne en los cuadros que pide, dada una dimensión de n centímetros de alto y m centímetros de ancho de un cuadro a pintar.

Para ello Melchor usa una paleta de varios colores los mismos que están identificados como números, donde el 1 es el color blanco que nunca es pintado.

El cuadro puede ser visto como una cuadricula de nxm cuadraditos cada uno de ellos de 1 cm. Por lo que, si se tiene un cuadro de 3x4, la cuadr´ıcula se enumera de izquierda a derecha y de arriba a abajo, empezando en 0; como se muestra en el Cuadro 1.

Cuadro 1: Ejemplo de ubicación de cuadriculas.

Como a Melchor le gustan los cuadros coloridos, a él le gustaría pintar cada espacio de la cuadricula con los colores desde 1 hasta Cn en orden creciente; sin embargo eso no es posible para no desperdiciar pintura. Para ello Melchor utiliza el hecho de que los colores se comportan de una manera particular. 

Si se quiere pintar la celda n se utiliza los colores de 1 a Cn, y para determinar el color de la celda se utiliza el dominio de colores sobre colores, de tal manera que los colores para cada posición i dominan al color i + 1 y así hasta Cn circularmente, esto quiere decir que el color del final puede dominar al color del inicio si se los ordenase en una línea. 

Por ejemplo, si se tuviera que pintar la quinta cuadricula del cuadro, se usan los siguientes colores {1,2,3,4,5}, como Melchor pinta con todos los colores posibles, estos colores cambiarían por la ley de dominio de colores de su estado inicial a {1,3,4,5} cuando 1 domina a 2, {1,3,5} cuando 3 domina a 4, {3,5} cuando 5 domina a 1, y finalmente {3} cuando 3 domina a 5. Por lo tanto, para la posición 5 del cuadro, Melchor sólo debe usar el color 3 para no desperdiciar pintura. Y ademas sólo usa colores de Mersenne, un color de Mersenne se identifica con un número que se obtiene con la formula 2k − 1, para algun k positivo. 

Tu tarea es ayudar a Melchor a determinar que colores usar en las obras que el virrey le encarga, y mostrar el cuadro resultante. Una característica de Melchor es que en la esquina superior izquierda del cuadro pone su firma artística la cual es mostrada como una 'M'.

Recordar que cuando Melchor no puede pintar un espacio del cuadro este es mostrado como un asterisco '*', esto sucede cuando el color dominante es el blanco o cuando no es un color de Mersenne.

Entrada

La primera línea contiene un número entero 1 ≤ t ≤ 100 que indica cuántas obras de arte pide el Virrey a Melchor.

Las siguientes t líneas contienen dos números enteros n y m que son las dimensiones de cada solicitud de obra de arte encargada a Melchor.

Salida

Para cada obra encargada a Melchor, muestra el número de cuadro y en las siguientes n líneas muestra los colores dominantes de cada celda, si la celda no tuviera un color dominante de Mersenne debe imprimirse un asterisco '*' indicando que el espacio de la cuadricula no es pintado, tomar en cuenta que la firma de Melchor es una 'M' y que el color blanco nunca es pintado.

Ejemplo de Entrada

3
3 4
4 3
2 4

Ejemplo de Salida

Cuadro 1
M**3
*3*7
*3*7
Cuadro 2
M**
3*3
*7*
3*7
Cuadro 3
M**3
*3*7

Código

OBI17FP6V2

Intentos de resolución

50
15

Logrados

Etiquetas

#obi-final-nacional #2017