Las vacas del granjero John disfrutan mucho tirando piedras al lago junto a su pastizal. Cuando una piedra toca la superficie, genera una ola que se propaga por ella.
La superficie es una gran cuadrícula de cuadrados. La profundidad de cada cuadrado depende de la interacción de las olas. Antes de tirar piedras, todos los cuadrados salvo los de las orillas originales del río tienen profundidad 0. Se representan así:
o: profundidad menor que 0.-: profundidad igual a 0.*: profundidad mayor que 0.X: parte de la orilla original del río.
Una piedra genera una ola de agua elevada que se extiende en forma de rombo y crece cada segundo. La profundidad de cada cuadrado del rombo aumenta en 1 durante un solo segundo. Dos segundos después le sigue una ola de agua descendida, que reduce la profundidad en 1 y también se extiende como un rombo. Cada piedra produce solo dos olas: elevada y luego descendida.
Por ejemplo, se muestra el efecto de una piedra caída en el centro del lago a los 0, 1, 2 y 3 segundos de caer:
0 seconds 1 second 2 seconds 3 seconds ------- ------- ------- ---*--- ------- ------- ---*--- --*-*-- ------- ---*--- --*-*-- -*-o-*- ---*--- --*-*-- -*-o-*- *-o-o-* ------- ---*--- --*-*-- -*-o-*- ------- ------- ---*--- --*-*-- ------- ------- ------- ---*---
Las columnas, de izquierda a derecha, corresponden a 0, 1, 2 y 3 segundos.
Las orillas tienen coordenadas $x$ fijas y recorren todo el lago de arriba abajo, con anchura de un cuadrado. Al llegar a una orilla, la ola no sigue a través de ella: continúa creciendo, pero se refleja la parte que la golpea.
Se muestran los primeros segundos de una ola al chocar con una orilla. Para mayor claridad, no se muestra la segunda ola de agua descendida:
1 second 2 seconds 3 seconds 4 seconds 5 seconds X------ X------ X--*--- X-*-*-- X*---*- X------ X--*--- X-*-*-- X*---*- X*----* X--*--- X-*-*-- X*---*- X*----* X-*---- X-*-*-- X*---*- X*----* X-*---- X--*--- X--*--- X-*-*-- X*---*- X*----* X-*---- X------ X--*--- X-*-*-- X*---*- X*----* X------ X------ X--*--- X-*-*-- X*---*-
Las columnas, de izquierda a derecha, corresponden a 1, 2, 3, 4 y 5 segundos.
Cuando partes de olas se encuentran, no afectan a su propagación mutua. En el siguiente instante crecerán como si no se hubieran encontrado. Sin embargo, sus efectos sobre el lago se combinan. Por ejemplo:
1 second 2 seconds 3 seconds 4 seconds --------- --------- --------- ---*----- --------- --------- ---*----- --*-*-*-- --------- ---*----- --*-*-*-- -*-o-*-*- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --*-*-*-- -*-o-*-*- *-o-----* -o-*-o--- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --------- ---*----- --*-*-*-- -*-o-*-*- --------- --------- ---*----- --*-*-*-- --------- --------- --------- ---*-----
Las columnas, de izquierda a derecha, corresponden a 1, 2, 3 y 4 segundos.
Escribe un programa para ayudar a las vacas a determinar cómo se propagan las olas con el tiempo.
Entrada
Línea 1: cuatro enteros $P$, $B1$, $B2$, $R$, separados por espacios.
$P$ ($1 \le P \le 5$) indica el número de piedras.
$B1$ ($-500{,}000 \le B1 \le 500{,}000$) y $B2$ ($-500{,}000 \le B2 \le 500{,}000$) son las coordenadas $x$ de las dos orillas.
$R$ ($1 \le R \le 500{,}000$) es el instante en el que se debe mostrar el lago.
Dos piedras no caerán a la vez en la misma posición. Las orillas tienen coordenadas $x$ distintas y ninguna piedra caerá sobre una orilla.
Líneas $2..P+1$: tres enteros separados por espacios describen una piedra: $X$ ($-500{,}000 \le X \le 500{,}000$), $Y$ ($-500{,}000 \le Y \le 500{,}000$) y $T$ ($1 \le T \le 500{,}000$).
$X$ y $Y$ son las coordenadas donde cae la piedra.
$T$ es el instante de su caída.
Salida
- Líneas 1 a 9: una cuadrícula $9 \times 9$ centrada en $(0,0)$. La esquina inferior izquierda representa $(-4,-4)$ y la superior derecha $(4,4)$. Debe representar el estado del lago en el instante $R$.
Ejemplos
Entrada 1
2 4 100 4 -3 0 1 0 0 2
Salida 1
--------X -*------X *-*-*---X -o-*-*--X o-----*-X -o-*-*--X *-*-*---X -*------X --------X
Autor del problema: Richard Forster, BIO 2003, 2003