Коровы фермера John обожают бросать камешки в озеро рядом с пастбищем. Когда камешек ударяется о поверхность озера, возникает волна, распространяющаяся по ней.
Поверхность озера представлена большой сеткой квадратов. Глубина воды в каждом квадрате определяется взаимодействием волн. До падения камешков глубина во всех квадратах, кроме исходных берегов реки, равна 0. Квадраты отображаются так:
o: глубина меньше 0.-: глубина равна 0.*: глубина больше 0.X: квадрат исходного берега реки.
Падение камешка вызывает волну поднятой воды, распространяющуюся ромбом, растущим каждую секунду. Глубина каждого квадрата на ромбе увеличивается на 1 ровно на одну секунду. Через две секунды следует волна опущенной воды, уменьшающая глубину на 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: выведите сетку $9 \times 9$ с центром в $(0,0)$. Нижний левый угол — $(-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