En uno de esos giros inesperados del multiverso, Karel apareció repentinamiente al inicio de un tunel. El tunel es un pasillo de ancho \(1\) que no tiene bifurcaciones. De alguna manera, Karel sabe que tiene que llegar al otro extremo del tunel lo más rápido posible.

Karel avanza \(C\) casillas por el tunel cada segundo. Pero hay una complicación, el tunel se inunda \(1\) fila cada segundo, es decir, al final del segundo uno, todas las casillas del tunel que están en la fila \(1\) quedarán inundadas. Al final del segundo dos, todas las casillas del tunel en la fila \(2\) o menores estarán inundadas, etc. Las casillas se inundan sin importar en qué parte del tunel estén.

Karel no sabe aguantar la respiración, por lo que si en algún momento pasa por una casilla que está inundada, se ahogará :(. Observa que cada segundo, Karel avanza las \(C\) casillas, Karel se ahogará si cualquiera de las \(C\) casillas por las que pasa ese segundo está inundada. Ayuda a Karel a determinar si será capaz de salir del tunel.

La casilla del tunel donde inicia Karel siempre está en la fila \(1\). En la posición inicial de Karel habrá un montón de zumbadores igual a \(C\), la cantidad de casillas que avanza Karel cada segundo. El tunel termina cuando Karel ya no puede seguir avanzando.

Problema

Escribe un programa que determine si Karel será capaz de salir del tunel a tiempo. Tu programa deberá dejar a Karel orientado al norte en caso de que sea posible escapar y orientado al sur en caso de que no.

Ejemplos

Entrada

Mundo de entrada

Salida

Mundo de salida

Descripción

La figura en el ejemplo de salida muestra la situación del tunel al final de cada uno de los primeros tres segundos. Karel llega al final del tunel antes del final del segundo \(4\) por lo que no se inunda ninguna otra casilla y Karel sobrevive.

Si por ejemplo, la cantidad de casillas que avanza Karel inicialmente fuera de \(5\), entonces al final del tercer segundo Karel estará en una casilla que se encuentra en la fila \(3\) y por lo tanto se ahogará.

Consideraciones

• Karel inicia en el principio del tunel y orientado en la dirección en la que debe avanzar.
• Karel inicia en una casilla que está en la fila \(1\).
• Karel lleva infinitos zumbadores en la mochila.
• En el mundo sólo hay un montón de zumbadores en la posición inicial de Karel.
• El pasillo que representa el tunel es de ancho y no tiene bifurcaciones.
• Para obtener los puntos, tu programa deberá apagar a Karel viendo al norte en caso de que logre salir a tiempo o viendo al sur si en algún momento se ahoga.

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): Karel inicia orientado al este y el pasillo es totalmente recto.
• (25 puntos): \(C=2\), Karel avanza \(2\) casillas cada segundo.
• (25 puntos): Conforme avanza por el pasillo, Karel nunca avanza al sur.
• (25 puntos): Sin ninguna restricción.

Fuente: OMIPS 2024 (Félix Rafael Horta Cuadrilla)