Di suatu tempat dalam galaksi yang sangat jauh, di planet Nibiru, Basilius, salah satu mahasiswa paling menjanjikan, menerima beasiswa khusus di Universitas Negeri Nibiru (NSU) yang bergengsi. Ia memutuskan membeli tempat tidur untuk kamar asramanya.

Ia menginginkan tempat tidur dengan volume sebesar mungkin, tetapi ukurannya terbatas — Basilius ingin menyisakan ruang di kamarnya untuk barang hasil belanjanya kelak.

Toko setempat dapat membuat tempat tidur apa pun, asalkan berbentuk balok. Namun, tidak semua tempat tidur dapat dibawa dari toko ke kamar asrama. Tempat tidur harus dibawa melalui portal yang menyerupai pintu persegi panjang biasa. Portal tegak lurus terhadap lantai. Melewati sebuah portal membawa Anda ke sekitar beberapa portal lain atau ke sebuah kamar. Bantu Basilius menghitung ukuran tempat tidur yang optimal untuk kamarnya. Jarak antarportal jauh lebih besar daripada ukuran kamar asrama.

Diasumsikan tempat tidur diorientasikan sehingga satu sisi tetap selalu sejajar lantai dan sisi tetap lainnya sejajar dengan bidang yang memuat portal saat ini.

Tempat tidur tidak akan diputar setelah diangkat untuk dibawa melalui portal menuju kamar.

Masukan

Baris pertama berkas masukan berisi tiga bilangan bulat $a,b,c$ yang membatasi ukuran tempat tidur. Salah satu dimensi (panjang, lebar, dan tinggi) tidak boleh melebihi $a$, dimensi lainnya tidak boleh melebihi $b$, dan dimensi sisanya tidak boleh melebihi $c$ ($1\le a,b,c\le 500$).

Baris berikutnya berisi satu bilangan bulat $n$ — jumlah portal di planet tersebut ($2\le n\le 500$). Portal diberi nomor dari $1$ hingga $n$. Portal di toko bernomor $1$, dan portal yang menuju kamar Basilius bernomor $n$.

Sebanyak $n$ baris berikutnya dalam berkas masukan menjelaskan portal Nibiru, satu per baris. Baris ke-$i$ menjelaskan portal ke-$i$ dan diawali tiga bilangan real yang dipisahkan spasi: $w_i,h_i,k_i$. Dua bilangan pertama menentukan lebar dan tinggi portal, sedangkan bilangan ketiga menyatakan jumlah portal yang dapat dicapai langsung dengan melewati portal tersebut ($1\le w_i,h_i\le 300$, $0\le k_i<n$). Lalu terdapat $k_i$ bilangan bulat yang semuanya berbeda $p_{ij}$, yaitu nomor portal yang dapat diakses langsung dari portal ke-$i$ ($1\le p_{ij}\le n$, $p_{ij}\ne i$).

Keluaran

Berkas keluaran harus berisi tiga bilangan bulat positif $x,y,z$ dalam urutan apa pun — ukuran tempat tidur bervolume maksimum yang dapat dibawa Basilius dari toko ke kamar asramanya. Jika ada beberapa pilihan dengan volume terbesar, cetak salah satunya. Dijamin ada solusi untuk masalah ini.

Contoh

Masukan 1

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

Keluaran 1

100 200 300

Masukan 2

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

Keluaran 2

200 300 300