הפרות של החקלאי 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