Quelque part dans une galaxie très, très lointaine, sur la planète Nibiru, Basilius, l’un des étudiants les plus prometteurs, a reçu une bourse spéciale à la prestigieuse université d’État de Nibiru (NSU). Il a décidé d’acheter un lit pour sa chambre en résidence universitaire.

Il veut un lit au volume le plus grand possible, mais les dimensions de son futur lit sont limitées : Basilius souhaite garder de la place dans sa chambre pour ses futurs trophées de shopping.

Le magasin local peut fabriquer n’importe quel lit, à condition qu’il soit un parallélépipède rectangle. Mais tous les lits ne peuvent pas être transportés du magasin à la chambre. Il faudra les porter à travers des portails ressemblant à nos portes rectangulaires habituelles. Les portails sont perpendiculaires au sol. Traverser un portail vous amène soit à proximité d’autres portails, soit dans une chambre. Aidez Basilius à calculer les dimensions optimales du lit pour sa chambre. La distance entre les portails est nettement supérieure aux dimensions de la chambre en résidence.

On suppose que le lit est orienté de telle sorte qu’une face fixe soit toujours parallèle au sol et qu’une autre face fixe soit parallèle au plan contenant le portail courant.

Le lit ne sera pas tourné une fois soulevé pour être transporté à travers les portails jusqu’à la chambre.

Entrée

La première ligne du fichier d’entrée contient trois entiers $a,b,c$ limitant les dimensions du lit. L’une des dimensions (longueur, largeur et hauteur) ne doit pas dépasser $a$, une autre ne doit pas dépasser $b$, et la dernière ne doit pas dépasser $c$ ($1\le a,b,c\le 500$).

La ligne suivante contient un unique entier $n$ : le nombre de portails sur la planète ($2\le n\le 500$). Les portails sont numérotés de $1$ à $n$. Le portail du magasin porte le numéro $1$ et celui qui mène à la chambre de Basilius porte le numéro $n$.

Les $n$ lignes suivantes du fichier d’entrée décrivent les portails de Nibiru, un par ligne. La $i$-ième ligne décrit le $i$-ième portail et commence par trois nombres réels séparés par des espaces : $w_i,h_i,k_i$. Les deux premiers définissent la largeur et la hauteur du portail, et le troisième indique le nombre de portails directement accessibles en traversant le portail décrit ($1\le w_i,h_i\le 300$, $0\le k_i<n$). Viennent ensuite $k_i$ entiers deux à deux distincts $p_{ij}$ : ils donnent les numéros des portails directement accessibles depuis le $i$-ième portail ($1\le p_{ij}\le n$, $p_{ij}\ne i$).

Sortie

Le fichier de sortie doit contenir trois entiers positifs $x,y,z$ dans un ordre quelconque : les dimensions du lit au volume maximal que Basilius peut transporter du magasin à sa chambre en résidence. Si plusieurs possibilités ont le volume maximal, affichez n’importe laquelle. L’existence d’une solution est garantie.

Exemples

Entrée 1

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

Sortie 1

100 200 300

Entrée 2

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

Sortie 2

200 300 300