Revolución P48510

Voy a cantar el corrido
de un hombre que fue a la guerra
y anduvo en la sierra herido
para conquistar su tierra.

Lo conocí en la batalla
y entre tanta balasera
el que es revolucionario
puede morir donde quiera.

El general nos decía
“Peleen con mucho valor;
les vamos a dar parcela
cuando haya repartición.”

Mi padre fue peón de hacienda
y yo un revolucionario
mis hijos pusieron tienda
y mi nieto es funcionario.

Gritó Emiliano Zapata
“Quiero tierra y libertad!”
y el gobierno se reía
cuando lo iban a enterrar.

Vuela, vuela palomita!
Paráte en aquella higuera
que acá se acaba el corrido
del mentado Juan Sin Tierra.

Juan Sin Tierra
Víctor Jara

Después de ganar la revolución, el general quiere cumplir sus promesas y repartir tierras entre sus guerrilleros. Para evitar problemas políticos, ha elegido un territorio salvaje con algunos claros. Su plan es soltar a los guerrilleros desde un avión en un claro suficientemente grande y dejarles encerrados. Su objetivo es confinarles en el menor territorio posible por si acaso valiere algun dinero, pero suficientemente grande para que los guerrilleros no se amotinen y empiecen otra revolución que le destrone.

Para esto, dispone de un mapa de la zona, rectangular, dónde ‘X’ denota árboles impenetrables y ‘.’ denota territorio transitable. Además, sabe que los guerrilleros se van a conformar con un territorio dónde haya al menos tantas casillas transitables como guerrilleros que sea accesibles a pie. Un guerrillero puede acceder desde una casilla a cualquiera de las 8 adyacentes siempre que no haya árboles. Además, puede caminar tanto como sea necesario. Se asume que fuera del mapa hay sólo jungla impenetrable.

Tu tarea es ayudar al malvado general a explotar eficientemente a su pueblo. Esto es, indicar el menor territorio que no cause más revolución.

Entrada

Cada caso empieza con una línea con tres numeros g, n y m donde g ≥ 0 es el número de guerrilleros, y 0 ≤ n,m ≤ 1000. A continuación, n líneas de m caracteres, todos ‘X’ o ‘.’.

Salida

Para cada caso, una línea con las coordenadas de un punto que cumpla las condiciones del general en el formato (x,y). Si hay más de uno, el menor lexicográficamente: el punto más a la izquierda y luego el superior. Si el general no puede cumplir su promesa, una línea con la palabra ‘REVOLUCION!’.