Krowy farmera John uwielbiają rzucać kamyki do jeziora obok pastwiska. Gdy kamyk uderza w powierzchnię, wywołuje falę, która rozchodzi się po niej.
Powierzchnia jeziora jest dużą siatką kwadratów. Głębokość wody w każdym zależy od oddziaływania fal. Przed rzuceniem kamyków każdy kwadrat poza pierwotnymi brzegami rzeki ma głębokość 0. Oznaczenia są następujące:
o: głębokość mniejsza od 0.-: głębokość równa 0.*: głębokość większa od 0.X: część pierwotnego brzegu rzeki.
Kamyk powoduje falę podniesionej wody rozchodzącą się w kształcie rombu rosnącego co sekundę. Głębokość każdego kwadratu na rombie wzrasta o 1 tylko na jedną sekundę. Dwie sekundy później następuje fala obniżonej wody, zmniejszająca głębokość o 1 i również rozchodząca się rombem. Każdy kamyk wywołuje tylko dwie fale, podniesioną, a potem obniżoną.
Przykładowo rysunek pokazuje efekt kamyka rzuconego w środek jeziora po 0, 1, 2 i 3 sekundach od upadku:
0 seconds 1 second 2 seconds 3 seconds ------- ------- ------- ---*--- ------- ------- ---*--- --*-*-- ------- ---*--- --*-*-- -*-o-*- ---*--- --*-*-- -*-o-*- *-o-o-* ------- ---*--- --*-*-- -*-o-*- ------- ------- ---*--- --*-*-- ------- ------- ------- ---*---
Kolumny od lewej do prawej odpowiadają 0, 1, 2 i 3 sekundom.
Brzegi mają stałe współrzędne $x$ i biegną przez całą długość jeziora od góry do dołu, na szerokość jednego kwadratu. Po dotarciu do brzegu fala nie przechodzi przez niego: rośnie dalej, lecz część uderzająca w brzeg odbija się.
Pokazano pierwsze sekundy fali uderzającej w jeden brzeg. Dla czytelności pominięto drugą falę obniżonej wody:
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*---*-
Kolumny od lewej do prawej odpowiadają 1, 2, 3, 4 i 5 sekundom.
Gdy fragmenty fal się spotykają, nie wpływają na wzajemne rozchodzenie. W następnym takcie rosną tak, jakby nie doszło do spotkania. Jednak ich wpływy na jezioro sumują się. Na przykład:
1 second 2 seconds 3 seconds 4 seconds --------- --------- --------- ---*----- --------- --------- ---*----- --*-*-*-- --------- ---*----- --*-*-*-- -*-o-*-*- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --*-*-*-- -*-o-*-*- *-o-----* -o-*-o--- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --------- ---*----- --*-*-*-- -*-o-*-*- --------- --------- ---*----- --*-*-*-- --------- --------- --------- ---*-----
Kolumny od lewej do prawej odpowiadają 1, 2, 3 i 4 sekundom.
Napisz program pomagający krowom ustalić, jak fale rozchodzą się w czasie.
Wejście
Wiersz 1: cztery liczby całkowite $P$, $B1$, $B2$, $R$, oddzielone spacjami.
$P$ ($1 \le P \le 5$) oznacza liczbę kamyków.
$B1$ ($-500{,}000 \le B1 \le 500{,}000$) i $B2$ ($-500{,}000 \le B2 \le 500{,}000$) są współrzędnymi $x$ dwóch brzegów.
$R$ ($1 \le R \le 500{,}000$) to czas, w którym należy wyświetlić jezioro.
Żadne dwa kamyki nie spadną w tym samym miejscu w tym samym czasie. Brzegi mają różne współrzędne $x$, a żaden kamyk nie spadnie na brzeg.
Wiersze $2..P+1$: trzy liczby całkowite oddzielone spacjami opisujące kamyk: $X$ ($-500{,}000 \le X \le 500{,}000$), $Y$ ($-500{,}000 \le Y \le 500{,}000$) i $T$ ($1 \le T \le 500{,}000$).
$X$ i $Y$ to współrzędne upadku kamyka.
$T$ to czas upadku kamyka.
Wyjście
- Wiersze 1–9: siatka $9 \times 9$ ze środkiem w $(0,0)$. Lewy dolny róg to $(-4,-4)$, prawy górny to $(4,4)$. Ma przedstawiać stan jeziora w czasie $R$.
Przykład
Wejście 1
2 4 100 4 -3 0 1 0 0 2
Wyjście 1
--------X -*------X *-*-*---X -o-*-*--X o-----*-X -o-*-*--X *-*-*---X -*------X --------X
Autor zadania: Richard Forster, BIO 2003, 2003