אי שם בגלקסיה רחוקה מאוד, על כוכב הלכת Nibiru, קיבל Basilius, אחד הסטודנטים המבטיחים ביותר, מלגה מיוחדת באוניברסיטה הממלכתית היוקרתית של Nibiru‏ (NSU). הוא החליט לקנות מיטה לחדרו במעונות.

הוא רוצה מיטה בעלת הנפח הגדול ביותר האפשרי, אך ממדי המיטה העתידית שלו מוגבלים: Basilius רוצה להשאיר בחדרו מקום לשלל הקניות העתידיות שלו.

החנות המקומית יכולה לייצר כל מיטה, בתנאי שצורתה תיבה מלבנית. אבל לא כל מיטה אפשר להעביר מהחנות לחדר במעונות. יהיה צורך לשאת אותה דרך שערים הדומים לדלתות המלבניות הרגילות שלנו. השערים ניצבים לרצפה. מעבר דרך שער מביא אתכם לקרבת שערים אחרים או לחדר. עזרו ל־Basilius לחשב את ממדי המיטה המיטביים לחדרו. המרחק בין השערים גדול במידה ניכרת מממדי החדר במעונות.

מניחים שהמיטה מכוונת כך שפאה קבועה אחת תמיד תהיה מקבילה לרצפה, ופאה קבועה אחרת תהיה מקבילה למישור המכיל את השער הנוכחי.

לא מסובבים את המיטה לאחר שמרימים אותה כדי לשאת אותה דרך השערים לחדר.

קלט

השורה הראשונה בקובץ הקלט מכילה שלושה מספרים שלמים $a,b,c$ המגבילים את ממדי המיטה. אחד הממדים (אורך, רוחב וגובה) חייב להיות לכל היותר $a$, ממד אחר לכל היותר $b$, והממד הנותר לכל היותר $c$ ($1\le a,b,c\le 500$).

השורה הבאה מכילה מספר שלם יחיד $n$ — מספר השערים בכוכב הלכת ($2\le n\le 500$). השערים ממוספרים מ־$1$ עד $n$. השער בחנות ממוספר $1$, והשער המוביל לחדרו של Basilius ממוספר $n$.

$n$ השורות הבאות בקובץ הקלט מתארות את שערי Nibiru, שער אחד בכל שורה. השורה ה־$i$ מתארת את השער ה־$i$ ומתחילה בשלושה מספרים ממשיים המופרדים ברווחים: $w_i,h_i,k_i$. השניים הראשונים מגדירים את רוחב השער ואת גובהו, והשלישי מציין את מספר השערים שאפשר להגיע אליהם ישירות במעבר דרך השער המתואר ($1\le w_i,h_i\le 300$, $0\le k_i<n$). אחריהם מופיעים $k_i$ מספרים שלמים $p_{ij}$ השונים זה מזה בזוגות: אלה מספרי השערים הנגישים ישירות מהשער ה־$i$ ($1\le p_{ij}\le n$, $p_{ij}\ne i$).

פלט

קובץ הפלט חייב להכיל שלושה מספרים שלמים חיוביים $x,y,z$ בסדר כלשהו — ממדי המיטה בעלת הנפח הגדול ביותר האפשרי ש־Basilius יכול להביא מהחנות לחדרו במעונות. אם יש כמה אפשרויות בעלות הנפח המרבי, הדפיסו אחת מהן. מובטח שקיים פתרון לבעיה.

דוגמאות

קלט 1

300 300 300
4
300 300 1 2
100 200 1 4
300 200 1 1
300 300 2 3 1

פלט 1

100 200 300

קלט 2

300 300 300
4
300 300 2 2 3
100 200 1 4
300 200 1 4
300 300 1 1

פלט 2

200 300 300