Десь у далекій-далекій галактиці на планеті 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