Gdzieś w odległej galaktyce, na planecie Nibiru, Basilius, jeden z najbardziej obiecujących studentów, otrzymał specjalne stypendium na prestiżowym Nibiriańskim Uniwersytecie Państwowym (NSU). Postanowił kupić łóżko do swojego pokoju w akademiku.

Chce łóżka o jak największej objętości, ale jego wymiary są ograniczone — Basilius chce zostawić w pokoju trochę miejsca na przyszłe zdobycze zakupowe.

Miejscowy sklep może wykonać dowolne łóżko, pod warunkiem że ma ono kształt prostopadłościanu. Nie każde łóżko da się jednak dostarczyć ze sklepu do pokoju w akademiku. Trzeba będzie przenieść je przez portale przypominające zwykłe prostokątne drzwi. Portale są prostopadłe do podłogi. Przejście przez portal przenosi w pobliże pewnych innych portali albo do pokoju. Pomóż Basiliusowi obliczyć optymalne wymiary łóżka do jego pokoju. Odległości między portalami są znacznie większe od rozmiarów pokoju w akademiku.

Zakłada się, że łóżko jest ustawione tak, aby jedna ustalona ściana była zawsze równoległa do podłogi, a inna ustalona ściana była równoległa do płaszczyzny zawierającej bieżący portal.

Po podniesieniu łóżka w celu przeniesienia go przez portale do pokoju nie będzie ono obracane.

Wejście

Pierwszy wiersz pliku wejściowego zawiera trzy liczby całkowite $a,b,c$ ograniczające wymiary łóżka. Jeden z wymiarów (długość, szerokość i wysokość) nie może przekraczać $a$, inny nie może przekraczać $b$, a pozostały nie może przekraczać $c$ ($1\le a,b,c\le 500$).

Następny wiersz zawiera jedną liczbę całkowitą $n$ — liczbę portali na planecie ($2\le n\le 500$). Portale są ponumerowane od $1$ do $n$. Portal w sklepie ma numer $1$, a portal prowadzący do pokoju Basiliusa ma numer $n$.

Następne $n$ wierszy pliku wejściowego opisuje portale Nibiru, po jednym w wierszu. Wiersz $i$ opisuje portal $i$ i zaczyna się od trzech liczb rzeczywistych oddzielonych spacjami: $w_i,h_i,k_i$. Pierwsze dwie określają szerokość i wysokość portalu, a trzecia oznacza liczbę portali, do których można dotrzeć bezpośrednio, przechodząc przez opisywany portal ($1\le w_i,h_i\le 300$, $0\le k_i<n$). Dalej następuje $k_i$ parami różnych liczb całkowitych $p_{ij}$: są to numery portali bezpośrednio dostępnych z portalu $i$ ($1\le p_{ij}\le n$, $p_{ij}\ne i$).

Wyjście

Plik wyjściowy musi zawierać trzy dodatnie liczby całkowite $x,y,z$ w dowolnej kolejności — wymiary łóżka o największej możliwej objętości, które Basilius może przenieść ze sklepu do swojego pokoju w akademiku. Jeśli istnieje kilka wariantów o największej objętości, wypisz dowolny z nich. Zagwarantowano istnienie rozwiązania.

Przykład

Wejście 1

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

Wyjście 1

100 200 300

Wejście 2

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

Wyjście 2

200 300 300