Algures numa galáxia muito, muito distante, no planeta Nibiru, Basilius, um dos estudantes mais promissores, recebeu uma bolsa especial na prestigiada Universidade Estatal de Nibiru (NSU). Decidiu comprar uma cama para o seu quarto na residência estudantil.

Quer uma cama com o maior volume possível, mas, por outro lado, as dimensões da futura cama são limitadas — Basilius quer guardar algum espaço no quarto para as suas futuras conquistas nas compras.

A loja local pode fabricar qualquer cama, desde que seja um paralelepípedo retângulo. Mas nem todas as camas podem ser levadas da loja para o quarto. Será necessário transportá-las através de portais que se assemelham às nossas portas retangulares comuns. Os portais são perpendiculares ao chão. Atravessar um portal leva às proximidades de outros portais ou a um quarto. Ajude Basilius a calcular as dimensões ideais da cama para o seu quarto. A distância entre portais é significativamente maior do que as dimensões do quarto na residência.

Supõe-se que a cama está orientada de modo que uma face fixa esteja sempre paralela ao chão e outra face fixa esteja paralela ao plano que contém o portal atual.

A cama não será rodada depois de ser levantada para ser transportada através dos portais até ao quarto.

Entrada

A primeira linha do ficheiro de entrada contém três inteiros $a,b,c$ que limitam as dimensões da cama. Uma das dimensões (comprimento, largura e altura) não pode exceder $a$, outra não pode exceder $b$ e a restante não pode exceder $c$ ($1\le a,b,c\le 500$).

A linha seguinte contém um único inteiro $n$ — o número de portais do planeta ($2\le n\le 500$). Os portais são numerados de $1$ a $n$. O portal da loja tem o número $1$ e o portal que conduz ao quarto de Basilius tem o número $n$.

As $n$ linhas seguintes do ficheiro de entrada descrevem os portais de Nibiru, um por linha. A linha $i$ descreve o portal $i$ e começa com três números reais separados por espaços — $w_i,h_i,k_i$. Os dois primeiros definem a largura e a altura do portal e o terceiro indica o número de portais a que se pode chegar diretamente atravessando o portal descrito ($1\le w_i,h_i\le 300$, $0\le k_i<n$). Seguem-se $k_i$ inteiros distintos dois a dois $p_{ij}$: indicam os números dos portais diretamente acessíveis a partir do portal $i$ ($1\le p_{ij}\le n$, $p_{ij}\ne i$).

Saída

O ficheiro de saída deve conter três inteiros positivos $x,y,z$ em qualquer ordem — as dimensões da cama com o maior volume possível que Basilius consegue levar da loja para o seu quarto na residência. Se houver várias opções com o volume máximo, imprima qualquer uma delas. É garantido que existe uma solução para o problema.

Exemplos

Entrada 1

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

Saída 1

100 200 300

Entrada 2

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

Saída 2

200 300 300