농부 John의 소들은 목초지 옆 호수에 작은 돌을 던지는 것을 무척 좋아합니다. 돌이 수면에 닿으면 수면을 따라 퍼지는 파도가 생깁니다.
수면은 커다란 정사각형 격자로 표현합니다. 각 칸의 수심은 파도의 상호작용으로 결정됩니다. 돌을 던지기 전에는 원래 강둑인 칸을 제외한 모든 칸의 수심이 0입니다. 다음과 같이 표시합니다.
o: 수심이 0보다 작은 칸.-: 수심이 0인 칸.*: 수심이 0보다 큰 칸.X: 원래 강둑인 칸.
돌을 떨어뜨리면 수면이 올라가는 파도가 매초 커지는 마름모 모양으로 퍼집니다. 마름모 위 각 칸의 수심은 단 1초 동안만 1 증가합니다. 2초 뒤에는 수면이 내려가는 파도가 뒤따라 수심을 1 줄이며 마찬가지로 마름모로 퍼집니다. 각 돌은 올라가는 파도, 그 다음 내려가는 파도 두 개만 만듭니다.
예를 들어 호수 중앙에 돌을 떨어뜨린 뒤 0, 1, 2, 3초가 지난 모습입니다.
0 seconds 1 second 2 seconds 3 seconds ------- ------- ------- ---*--- ------- ------- ---*--- --*-*-- ------- ---*--- --*-*-- -*-o-*- ---*--- --*-*-- -*-o-*- *-o-o-* ------- ---*--- --*-*-- -*-o-*- ------- ------- ---*--- --*-*-- ------- ------- ------- ---*---
그림의 열은 왼쪽부터 0, 1, 2, 3초입니다.
강둑은 고정된 $x$ 좌표를 가지며 폭 한 칸으로 호수 전체 길이를 위에서 아래까지 이어집니다. 파도가 강둑에 닿으면 그대로 통과하지 않고 계속 커지되 강둑에 부딪힌 부분이 반사됩니다.
한 강둑에 부딪히는 파도의 처음 몇 초를 보여 줍니다. 보기 쉽도록 두 번째로 내려가는 파도는 생략했습니다.
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*---*-
그림의 열은 왼쪽부터 1, 2, 3, 4, 5초입니다.
파도 일부가 만나도 서로의 전파 방식에는 영향이 없습니다. 다음 시각에는 만나지 않았던 것처럼 커집니다. 하지만 호수에 미치는 영향은 합쳐집니다. 예를 들면 다음과 같습니다.
1 second 2 seconds 3 seconds 4 seconds --------- --------- --------- ---*----- --------- --------- ---*----- --*-*-*-- --------- ---*----- --*-*-*-- -*-o-*-*- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --*-*-*-- -*-o-*-*- *-o-----* -o-*-o--- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --------- ---*----- --*-*-*-- -*-o-*-*- --------- --------- ---*----- --*-*-*-- --------- --------- --------- ---*-----
그림의 열은 왼쪽부터 1, 2, 3, 4초입니다.
시간에 따라 파도가 어떻게 퍼지는지 소들에게 알려 주는 프로그램을 작성하세요.
입력
1번째 줄: 공백으로 구분된 네 정수 $P$, $B1$, $B2$, $R$.
$P$ ($1 \le P \le 5$)은 돌의 개수입니다.
$B1$ ($-500{,}000 \le B1 \le 500{,}000$)와 $B2$ ($-500{,}000 \le B2 \le 500{,}000$)는 두 강둑의 $x$ 좌표입니다.
$R$ ($1 \le R \le 500{,}000$)은 호수를 표시할 시각입니다.
두 돌이 같은 시각에 같은 위치로 떨어지는 일은 없습니다. 두 강둑의 $x$ 좌표는 다르며 돌은 강둑에 떨어지지 않습니다.
$2..P+1$번째 줄: 각 줄에 돌을 나타내는 공백으로 구분된 세 정수 $X$ ($-500{,}000 \le X \le 500{,}000$), $Y$ ($-500{,}000 \le Y \le 500{,}000$), $T$ ($1 \le T \le 500{,}000$).
$X$와 $Y$는 돌이 떨어지는 위치의 좌표입니다.
$T$는 돌이 떨어지는 시각입니다.
출력
- 1번째 줄부터 9번째 줄: $(0,0)$이 중심인 $9 \times 9$ 격자. 왼쪽 아래는 $(-4,-4)$, 오른쪽 위는 $(4,4)$입니다. 시각 $R$의 호수 상태를 나타내야 합니다.
예제
입력 1
2 4 100 4 -3 0 1 0 0 2
출력 1
--------X -*------X *-*-*---X -o-*-*--X o-----*-X -o-*-*--X *-*-*---X -*------X --------X
문제 출처: Richard Forster, BIO 2003, 2003