Các cô bò của nông dân John rất thích ném sỏi vào hồ bên cạnh đồng cỏ. Khi sỏi chạm mặt hồ, nó tạo ra một sóng lan truyền trên mặt hồ.
Mặt hồ là một lưới ô vuông lớn. Độ sâu mỗi ô do tương tác của sóng quyết định. Trước khi thả sỏi, mọi ô trừ các ô bờ sông ban đầu có độ sâu 0. Các ô được biểu diễn như sau:
o: độ sâu nhỏ hơn 0.-: độ sâu bằng 0.*: độ sâu lớn hơn 0.X: ô thuộc bờ sông ban đầu.
Một viên sỏi tạo sóng nước dâng lan ra thành hình thoi lớn lên mỗi giây. Độ sâu mỗi ô trên hình thoi tăng 1 chỉ trong một giây. Hai giây sau, một sóng nước hạ theo sau, giảm độ sâu 1 và cũng lan thành hình thoi. Mỗi viên sỏi chỉ tạo hai sóng, dâng rồi hạ.
Ví dụ, hình cho thấy tác động của viên sỏi rơi giữa hồ sau 0, 1, 2, 3 giây kể từ lúc rơi:
0 seconds 1 second 2 seconds 3 seconds ------- ------- ------- ---*--- ------- ------- ---*--- --*-*-- ------- ---*--- --*-*-- -*-o-*- ---*--- --*-*-- -*-o-*- *-o-o-* ------- ---*--- --*-*-- -*-o-*- ------- ------- ---*--- --*-*-- ------- ------- ------- ---*---
Các cột từ trái sang phải lần lượt là 0, 1, 2, 3 giây.
Các bờ có tọa độ $x$ cố định, kéo dài suốt chiều dài hồ từ trên xuống dưới, rộng một ô. Khi sóng chạm bờ, nó không đi xuyên qua: vẫn lớn lên nhưng phần chạm bờ bị phản xạ.
Hình cho thấy những giây đầu của sóng chạm một bờ. Để hình rõ hơn, không vẽ sóng nước hạ thứ hai:
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*---*-
Các cột từ trái sang phải lần lượt là 1, 2, 3, 4, 5 giây.
Khi các phần sóng gặp nhau, chúng không ảnh hưởng cách lan truyền của nhau. Tại nhịp thời gian tiếp theo, chúng lớn lên như chưa từng gặp. Tuy nhiên, tác động của chúng lên hồ được cộng lại. Ví dụ:
1 second 2 seconds 3 seconds 4 seconds --------- --------- --------- ---*----- --------- --------- ---*----- --*-*-*-- --------- ---*----- --*-*-*-- -*-o-*-*- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --*-*-*-- -*-o-*-*- *-o-----* -o-*-o--- ---*----- --*-*-*-- -*-o-*-*- *-o-----* --------- ---*----- --*-*-*-- -*-o-*-*- --------- --------- ---*----- --*-*-*-- --------- --------- --------- ---*-----
Các cột từ trái sang phải lần lượt là 1, 2, 3, 4 giây.
Viết chương trình giúp bò biết sóng lan ra thế nào theo thời gian.
Dữ liệu vào
Dòng 1: bốn số nguyên $P$, $B1$, $B2$, $R$, cách nhau bởi dấu cách.
$P$ ($1 \le P \le 5$) là số viên sỏi.
$B1$ ($-500{,}000 \le B1 \le 500{,}000$) và $B2$ ($-500{,}000 \le B2 \le 500{,}000$) là tọa độ $x$ của hai bờ.
$R$ ($1 \le R \le 500{,}000$) là thời điểm cần hiển thị hồ.
Không có hai viên sỏi rơi cùng vị trí cùng lúc. Hai bờ có tọa độ $x$ khác nhau và không viên sỏi nào rơi trên bờ.
Các dòng $2..P+1$: mỗi dòng ba số nguyên cách nhau bởi dấu cách mô tả một viên sỏi: $X$ ($-500{,}000 \le X \le 500{,}000$), $Y$ ($-500{,}000 \le Y \le 500{,}000$), $T$ ($1 \le T \le 500{,}000$).
$X$ và $Y$ là tọa độ nơi sỏi rơi.
$T$ là thời điểm sỏi rơi.
Dữ liệu ra
- Các dòng 1 đến 9: lưới $9 \times 9$ tâm $(0,0)$. Góc dưới trái biểu diễn $(-4,-4)$ và góc trên phải $(4,4)$. Lưới phải thể hiện hồ tại thời điểm $R$.
Ví dụ
Dữ liệu vào 1
2 4 100 4 -3 0 1 0 0 2
Dữ liệu ra 1
--------X -*------X *-*-*---X -o-*-*--X o-----*-X -o-*-*--X *-*-*---X -*------X --------X
Tác giả bài toán: Richard Forster, BIO 2003, 2003