Los arqueólogos han descubierto la ruina de un castillo medieval en una meseta montañosa, que fotografiaron desde el helicóptero, obteniendo un mapa digitalizado. El mapa se almacena en forma de una imagen ~H~ bidimensional, compuesta por un cuadrado ~NxN~ con el lado igual a la unidad, teniendo como elementos naturales entre ~0~ y ~15~, la codificación de la forma de las paredes de cada cuadrado unitario. Si escribimos el número natural ~H[i][j]~ en base 2, usando exactamente 4 dígitos binarios, cada bit proporciona información sobre una de las paredes posibles para construir en cada lado del cuadrado de la unidad desde la posición ~(i, j)~, de la siguiente manera:

• si el bit en la posición 0 es 1, entonces hay una pared en el lado oeste (lado izquierdo);

• Si el bit en la posición 1 es 1, entonces hay un muro en el lado sur (lado inferior);

• Si el bit en la posición 2 es 1, entonces hay un muro en el lado este (lado derecho);

• Si el bit en la posición 3 es 1, entonces hay una pared en el lado norte (lado superior);

• un bit de valor de 0 indica que no hay una pared correspondiente a él;

Para un número escrito en Base 2, los dígitos comienzan con la posición 0, de derecha a izquierda.

El castillo es interesante porque, para una mejor defensa, las cámaras que lo componen están construidas independientemente o dentro de la otra. Cada habitación está construida a una distancia de al menos una unidad de la pared que rodea el castillo o de las paredes de otras habitaciones. Usando el mapa, los arqueólogos quieren encontrar información sobre el número de habitación y el espacio máximo de la habitación. A través del área de una habitación se entiende el número de cuadrados contenidos dentro de las paredes, sin contar las áreas de las cámaras construidas en su interior.

Tarea

Conociendo el mapa codificado del castillo, determine:

1. El número total de cámaras en el castillo.
2. El área máxima de una habitación.
3. Las coordenadas de las esquinas superior izquierda e inferior derecha de la sala con el área máxima. Si hay más se muestran muchas habitaciones con la misma área máxima, luego se muestran las coordenadas de la habitación con la esquina izquierda (lin1, col1) con una línea mínima1 y con líneas iguales a la col1 mínima.

Entrada

Los datos de la entrada tienen la siguiente estructura:

• La primera línea es el número natural ~C~, que puede ser ~1~, ~2~ o ~3~, según el requisito a resolver;

• En la siguiente línea está el número natural ~N~ que representa el tamaño del mapa;

• Las siguientes ~N~ líneas contienen ~N~ números naturales en el rango ~[0, 15]~, separados por un espacio, representando el mapa del castillo.

Salida

Los datos de salida se escribirán de la siguiente manera:

• Si ~C = 1~, la primera línea escribirá el número total de cámaras en el castillo;

• Si ~C = 2~, la primera línea escribirá el área máxima de una sala del castillo;

• Si ~C = 3~, en la primera línea se escribirán 4 números naturales lin1 col1 lin2 col2, separados por cada un espacio, que representa las esquinas de las esquinas superior izquierda e inferior derecha de la habitación máxima.

Restricciones y aclaraciones:

• ~2 < N \le 100~

• Se garantiza que hay al menos una habitación en el castillo;

• Las pruebas que tienen ~C = 1~ suman ~30~ puntos;

• Las pruebas que tienen ~C = 2~ suman ~50~ puntos;

• Las pruebas que tienen ~C = 3~ suman ~20~ puntos;

Ejemplo de Entrada #1

1
9
0 2 0 0 0 0 0 0 0
4 15 1 0 0 2 2 0 0
0 10 2 0 4 11 14 1 0
4 9 12 1 2 10 10 2 0
4 3 6 5 9 8 10 12 1
0 10 8 4 1 4 15 5 1
4 13 1 4 3 2 10 6 1
4 7 1 0 8 8 8 8 0
0 8 0 0 0 0 0 0 0

Ejemplo de Salida #1

6

https://drive.google.com/open?id=1_9GheVDOUHsVXvNPJHXwfXSCzK1229_J

Explicación: La figura muestra el mapa del castillo codificado en el archivo de entrada. Consta de 6 habitaciones.

Ejemplo de Entrada #2

2
9
0 2 0 0 0 0 0 0 0
4 15 1 0 0 2 2 0 0
0 10 2 0 4 11 14 1 0
4 9 12 1 2 10 10 2 0
4 3 6 5 9 8 10 12 1
0 10 8 4 1 4 15 5 1
4 13 1 4 3 2 10 6 1
4 7 1 0 8 8 8 8 0
0 8 0 0 0 0 0 0 0

Ejemplo de Salida #2

11

Explicación: El área máxima de una habitación es de 11.

Ejemplo de Entrada #3

3
9
0 2 0 0 0 0 0 0 0
4 15 1 0 0 2 2 0 0
0 10 2 0 4 11 14 1 0
4 9 12 1 2 10 10 2 0
4 3 6 5 9 8 10 12 1
0 10 8 4 1 4 15 5 1
4 13 1 4 3 2 10 6 1
4 7 1 0 8 8 8 8 0
0 8 0 0 0 0 0 0 0

Ejemplo de Salida #3

5 5 7 8

Explicación: La habitación con el área máxima tiene coordenadas. (5,5) - (7,8)