Un laboratorio de investigación distribuye una colonia de bacterias en un cultivo, que se puede considerar como una superficie cuadriculada de N filas y N columnas; cada casilla de esta superficie puede estar vacía o puede contener una bacteria. A partir de cualquier configuración inicial, la colonia evoluciona generación a generación según unas leyes genéticas fijas y determinadas y que dependen del número de vecinos que tenga cada casilla.

Para todas y cada una de las generaciones las leyes genéticas son:
- Nacimiento: en toda casilla vacía que tenga exactamente tres vecinos.
- Muerte por aislamiento: toda bacteria que ocupe una casilla con uno o ningún vecinos.
- Muerte por asfixia: toda bacteria que ocupe una casilla con más de tres vecinos.
- Supervivencia: toda bacteria que ocupe una casilla con dos o tres vecinos.

La casilla que ocupa la fila i y la columna j se identifica mediante (i, j) (1<=i<=N, 1<=j<=N). Los vecinos de una casilla (i, j) son las posiciones (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j) e (i+1, j+1) que estén comprendidas dentro de la superficie y que estén ocupadas por una bacteria. Así, en una superficie 4x4, la colonia de la izquierda de la figura siguiente evoluciona en las dos próximas generaciones tal y como se muestra:

Se pide simular la evolución de una colonia inicial durante un cierto número de transiciones.

Entrada

Residente en el fichero de caracteres "COLO.DAT":
- Línea 1: valor de N (uno o dos caracteres que representen un número entero entre 1 y 20)
- Línea 2: número de transiciones a estudiar (varios caracteres que representen un número entero no negativo)
- Líneas siguientes: cada línea contiene una pareja de uno o dos caracteres, para representar la posición que ocupa una bacteria en la configuración inicial de la colonia. Los dos elementos de la pareja estarán separados por un único blanco. Cada elemento de la pareja representa pues un número comprendido entre 1 y N. Así, si N = 13, son ejemplos válidos las líneas:

3 4
12 3
5 13
13 13

Salida

A guardar en el fichero de caracteres "COLO.OUT": la colonia resultante de aplicar las reglas descritas en el enunciado. Representamos la colonia con N líneas de N caracteres. Cada carácter de esta superficie N x N será o bien un carácter 'o' (letra 'o') o bien un carácter 'x', según la casilla correspondiente esté vacía o bien ocupada por una bacteria, respectivamente.

Ejemplo de entrada

El ejemplo que aparece en la figura anterior (tablero 4 x 4 con 2 transiciones) se puede representar con el fichero de entrada siguiente:

4
2
1 3
2 2
2 3
3 3
4 3

Ejemplo de salida

oxox
oooo
oxox
oooo