Irgendwo in einer weit, weit entfernten Galaxie hat Basilius auf dem Planeten Nibiru als einer der vielversprechendsten Studenten ein besonderes Stipendium an der angesehenen Staatlichen Universität von Nibiru (NSU) erhalten. Er hat beschlossen, ein Bett für sein Wohnheimzimmer zu kaufen.

Er möchte ein Bett mit möglichst großem Volumen, doch seine Abmessungen sind begrenzt: Basilius möchte in seinem Zimmer noch Platz für seine zukünftigen Einkaufstrophäen lassen.

Im örtlichen Geschäft kann jedes Bett angefertigt werden, solange es ein Quader ist. Allerdings lässt sich nicht jedes Bett vom Geschäft ins Wohnheimzimmer bringen. Es muss durch Portale getragen werden, die unseren gewöhnlichen rechteckigen Türen ähneln. Die Portale stehen senkrecht zum Boden. Durch ein Portal gelangt man entweder in die Nähe einiger anderer Portale oder in ein Zimmer. Hilf Basilius, die optimalen Bettabmessungen für sein Zimmer zu berechnen. Der Abstand zwischen Portalen ist wesentlich größer als die Abmessungen des Wohnheimzimmers.

Es wird angenommen, dass das Bett so ausgerichtet ist, dass eine feste Seitenfläche immer parallel zum Boden und eine andere feste Seitenfläche parallel zur Ebene des aktuellen Portals ist.

Nachdem das Bett zum Transport durch die Portale ins Zimmer angehoben wurde, wird es nicht mehr gedreht.

Eingabe

Die erste Zeile der Eingabedatei enthält drei ganze Zahlen $a,b,c$, die die Bettabmessungen begrenzen. Eine der Abmessungen (Länge, Breite und Höhe) darf $a$ nicht überschreiten, eine andere darf $b$ nicht überschreiten und die verbleibende darf $c$ nicht überschreiten ($1\le a,b,c\le 500$).

Die nächste Zeile enthält eine ganze Zahl $n$ — die Anzahl der Portale auf dem Planeten ($2\le n\le 500$). Die Portale sind von $1$ bis $n$ nummeriert. Das Portal im Geschäft hat die Nummer $1$, das Portal zu Basilius’ Zimmer die Nummer $n$.

Die nächsten $n$ Zeilen der Eingabedatei beschreiben die Portale von Nibiru, eines pro Zeile. Die $i$-te Zeile beschreibt das $i$-te Portal und beginnt mit drei durch Leerzeichen getrennten reellen Zahlen $w_i,h_i,k_i$. Die ersten beiden geben Breite und Höhe des Portals an, die dritte die Anzahl der Portale, die durch das beschriebene Portal direkt erreichbar sind ($1\le w_i,h_i\le 300$, $0\le k_i<n$). Danach folgen $k_i$ paarweise verschiedene ganze Zahlen $p_{ij}$: die Nummern der direkt vom $i$-ten Portal erreichbaren Portale ($1\le p_{ij}\le n$, $p_{ij}\ne i$).

Ausgabe

Die Ausgabedatei muss drei positive ganze Zahlen $x,y,z$ in beliebiger Reihenfolge enthalten — die Abmessungen des Bettes mit dem größtmöglichen Volumen, das Basilius vom Geschäft in sein Wohnheimzimmer bringen kann. Gibt es mehrere Varianten mit maximalem Volumen, gib eine beliebige davon aus. Es ist garantiert, dass eine Lösung existiert.

Beispiele

Eingabe 1

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

Ausgabe 1

100 200 300

Eingabe 2

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

Ausgabe 2

200 300 300