Где-то в далёкой-далёкой галактике на планете 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