Karel está incursionando en el mercado de comida gourmet y acaba de abrir una tienda de quesos europeos. Muy pronto se dió cuenta de que a la gente en México no le gusta tanto que el queso traiga hoyos, ya que sienten que están pagando por aire.

Claro que Karel no se va a dar por vencido tan fácil. Siempre creativo y emprendedor, Karel ha decidido rellenar cada uno de los huecos de la tonelada de queso que acababa de comprar.

El mundo de Karel es un rectángulo sin paredes internas. En el mundo hay montones de 1 zumbador que representan el queso que Karel quiere rellenar. El queso puede tener cualquier forma al igual que los huecos internos. Se considera hueco un área sin zumbadores que esté totalmente rodeada de zumbadores.

La imagen de ejemplo muestra un posible queso. El queso está en color amarillo, los huecos están en color azul. En color rojo están marcadas casillas que no deben ser consideradas como un hueco ya que no están totalmente rodeadas por queso.

Ayuda a Karel escribiendo un programa que llene todos los huecos de su queso.

Problema

Escribe un programa que dado el queso de Karel, rellene todos sus huecos con montones de un zumbador. Tu programa debe dejar en el mundo todos los zumbadores del queso y no debe poner ningún zumbador fuera del queso.

Ejemplos

Entrada

Salida

Descripción

El mundo de entrada es el queso de la figura de ejemplo. Karel debe rellenar los huecos con montones de \(1\) zumbador sin alterar los zumbadores del queso ni agregar ningún otro zumbador en el mundo.

Consideraciones

• Karel inicia en la posición (1, 1) orientado al norte.
• Karel lleva infinitos zumbadores en la mochila.
• En el mundo sólo hay montones de \(1\) zumbador que representan el queso. El queso puede tener cualquier forma y puede tocar las paredes del mundo.
• Los huecos del queso pueden tener cualquier forma y siempre estarán totalmente rodeados de queso (montones de \(1\) zumbador).
• El mundo de Karel es un rectángulo sin paredes internas. Para obtener los puntos, tu programa deberá rellenar todos los huecos del queso sin alterar ningún zumbador de los que hay originalmente en el mundo.

Subtareas

En este problema, los casos de cada subtarea se encuentran agrupados. Para obtener el puntaje de una subtarea deberás resolver correctamente todos los casos del grupo.

• (25 puntos): El queso es rectangular y llena por completo el mundo.
• (25 puntos): El queso es rectangular.
• (25 puntos): Los huecos del queso son todos de 1 casilla.

• (25 puntos): Sin ninguna restricción.

  (Félix Rafael Horta Cuadrilla)