ณ ที่แห่งหนึ่งในกาแล็กซีอันไกลโพ้น บนดาวเคราะห์ 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