As vacas do fazendeiro John adoram jogar pedrinhas no lago ao lado do pasto. Quando uma pedra atinge a superfície, gera uma onda que se propaga por ela.
A superfície é uma grande grade de quadrados. A profundidade de cada quadrado depende da interação das ondas. Antes das pedras, todos os quadrados, exceto os das margens originais do rio, têm profundidade 0. São exibidos assim:
o: profundidade menor que 0.-: profundidade igual a 0.*: profundidade maior que 0.X: parte da margem original do rio.
Uma pedra gera uma onda de água elevada que se espalha como um losango, crescendo a cada segundo. A profundidade de cada quadrado do losango aumenta em 1 por apenas um segundo. Dois segundos depois segue uma onda de água rebaixada, diminuindo a profundidade em 1, também em losango. Cada pedra causa apenas duas ondas, elevada e depois rebaixada.
Por exemplo, a figura mostra o efeito de uma pedra caída no meio do lago, 0, 1, 2 e 3 segundos após a queda:
0 seconds 1 second 2 seconds 3 seconds ------- ------- ------- ---*--- ------- ------- ---*--- --*-*-- ------- ---*--- --*-*-- -*-o-*- ---*--- --*-*-- -*-o-*- *-o-o-* ------- ---*--- --*-*-- -*-o-*- ------- ------- ---*--- --*-*-- ------- ------- ------- ---*---
As colunas da esquerda para a direita são 0, 1, 2 e 3 segundos.
As margens têm coordenadas $x$ fixas e percorrem todo o lago de cima a baixo, com largura de um quadrado. Ao atingir uma margem, a onda não a atravessa: continua crescendo, mas a parte que bate na margem é refletida.
A figura mostra os primeiros segundos de uma onda atingindo uma margem. Para maior clareza, a segunda onda de água rebaixada não é mostrada:
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*---*-
As colunas da esquerda para a direita são 1, 2, 3, 4 e 5 segundos.
Quando partes das ondas se encontram, não afetam a propagação uma da outra. No próximo instante, crescem como se não houvesse encontro. Porém, seus efeitos no lago se combinam. Por exemplo:
1 second 2 seconds 3 seconds 4 seconds --------- --------- --------- ---*----- --------- --------- ---*----- --*-*-*-- --------- ---*----- --*-*-*-- -*-o-*-*- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --*-*-*-- -*-o-*-*- *-o-----* -o-*-o--- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --------- ---*----- --*-*-*-- -*-o-*-*- --------- --------- ---*----- --*-*-*-- --------- --------- --------- ---*-----
As colunas da esquerda para a direita são 1, 2, 3 e 4 segundos.
Escreva um programa para ajudar as vacas a descobrir como as ondas se espalham com o tempo.
Entrada
Linha 1: quatro inteiros $P$, $B1$, $B2$, $R$, separados por espaços.
$P$ ($1 \le P \le 5$) indica o número de pedras.
$B1$ ($-500{,}000 \le B1 \le 500{,}000$) e $B2$ ($-500{,}000 \le B2 \le 500{,}000$) são as coordenadas $x$ das duas margens.
$R$ ($1 \le R \le 500{,}000$) é o instante em que se deve exibir o lago.
Duas pedras não caem na mesma posição ao mesmo tempo. As margens têm coordenadas $x$ distintas, e nenhuma pedra cai sobre uma margem.
Linhas $2..P+1$: três inteiros separados por espaços descrevendo uma pedra: $X$ ($-500{,}000 \le X \le 500{,}000$), $Y$ ($-500{,}000 \le Y \le 500{,}000$) e $T$ ($1 \le T \le 500{,}000$).
$X$ e $Y$ são as coordenadas da queda da pedra.
$T$ é o instante da queda.
Saída
- Linhas 1 a 9: uma grade $9 \times 9$ centrada em $(0,0)$. O canto inferior esquerdo representa $(-4,-4)$ e o superior direito $(4,4)$. Deve mostrar o estado do lago no instante $R$.
Exemplos
Entrada 1
2 4 100 4 -3 0 1 0 0 2
Saída 1
--------X -*------X *-*-*---X -o-*-*--X o-----*-X -o-*-*--X *-*-*---X -*------X --------X
Autor do problema: Richard Forster, BIO 2003, 2003