Tres-Veltör recibió una consola de videojuegos por Navidad. No era una Playstation 4 ni una Xbox one, sino una Atari 2600, y venía con un juego gratis. El protagonista del juego está parado en la parte inferior de la pantalla, y hay varios objetos dispersos en el resto de la pantalla, cayendo hacia abajo.

Más precisamente, la pantalla se puede representar como una cuadrícula de ~F \times C~ píxeles dispuestos en ~F~ filas y ~C~ columnas. El protagonista ocupa un píxel de la línea más baja y se marca con M. El resto de los píxeles se marcan con los caracteres: . (espacio en blanco), * (bomba), ( (paréntesis abierto) o ) (paréntesis cerrado).

El protagonista puede moverse un píxel a la izquierda o a la derecha en un solo movimiento, pero no tiene por qué, mientras que el resto de los objetos se mueven simultáneamente un píxel hacia abajo (posiblemente fuera de la pantalla). Cuando el protagonista se encuentra en la misma posición que uno de los paréntesis, decimos que ha recogido ese paréntesis y lo ha agregado al final de su matriz de paréntesis adquiridos. El objetivo del protagonista es adquirir la expresión de paréntesis válida más larga posible.

Una expresión de paréntesis válida se define inductivamente de la siguiente manera:

• () es una expresión válida
• Si a es una expresión válida, entonces (a) también lo es
• Si a y b son expresiones válidas, entonces ab también lo es

El juego termina cuando el protagonista se encuentra en la misma posición que la bomba o cuando todos los objetos salen de la pantalla.

Entrada

La primera línea contiene los números ~F~ y ~C~ (~1 \leq F, C \leq 300~) que representan las dimensiones de la pantalla.

Cada una de las siguientes ~F~ líneas contiene ~C~ caracteres M, ., *, ( o ) que representan el estado inicial de la pantalla.

Los datos de prueba serán tales que siempre existirá al menos una expresión de paréntesis válida que sea posible adquirir.

Salida

En la primera línea, debe salir la longitud de la expresión de paréntesis válida más larga que Mirko puede adquirir. En la segunda línea, salga esa expresión. Si hay múltiples expresiones válidas más largas, salga la lexicográficamente más pequeña.

Puntuación

En casos de prueba que valen ~25%~ del total de puntos, se cumplirá que ~1 \leq F \leq 15~.

En casos de prueba que valen ~50%~ del total de puntos, se cumplirá que ~1 \leq F \leq 100~.

Ejemplo #1 de Entrada

5 4
..).
.)(.
(.)*
*(.*
..M.

Ejemplo #1 de Salida

4
(())

Explicación para la Entrada #1 de Ejemplo

Los movimientos del protagonista son: izquierda, izquierda, derecha, derecha.

Ejemplo #2 de Entrada

6 3
)(.
*..
(**
)()
().
M..

Ejemplo #2 de Salida

4
()()

Explicación para la Entrada #2 de Ejemplo

Los movimientos del protagonista son: quedarse quieto, quedarse quito, quedarse quieto, derecha, izquierda.

Ejemplo #3 de Entrada

6 3
((.
*..
(**
)()
().
M..

Ejemplo #3 de Salida

2
()

Explicación para la Entrada #3 de Ejemplo

Los movimientos del protagonista son: quedarse quieto, quedarse quieto, derecha.