Ở đâu đó trong một thiên hà xa xôi, trên hành tinh Nibiru, Basilius, một trong những sinh viên triển vọng nhất, đã nhận được học bổng đặc biệt tại Đại học Quốc gia Nibiru (NSU) danh tiếng. Cậu quyết định mua một chiếc giường cho phòng ký túc xá của mình.

Cậu muốn chiếc giường có thể tích lớn nhất có thể, nhưng kích thước của nó bị giới hạn — Basilius muốn dành một ít không gian trong phòng cho những chiến lợi phẩm mua sắm sau này.

Cửa hàng địa phương có thể làm bất kỳ chiếc giường nào, miễn là nó có dạng hình hộp chữ nhật. Nhưng không phải chiếc giường nào cũng có thể được chuyển từ cửa hàng đến phòng ký túc xá. Nó phải được khiêng qua các cổng dịch chuyển trông giống những cánh cửa hình chữ nhật thông thường. Các cổng vuông góc với sàn nhà. Đi qua một cổng sẽ đưa bạn đến gần một số cổng khác hoặc vào một căn phòng. Hãy giúp Basilius tính kích thước giường tối ưu cho phòng của cậu. Khoảng cách giữa các cổng lớn hơn đáng kể so với kích thước phòng ký túc xá.

Giả sử giường được định hướng sao cho một mặt cố định luôn song song với sàn nhà và một mặt cố định khác song song với mặt phẳng chứa cổng hiện tại.

Giường sẽ không bị xoay sau khi được nhấc lên để khiêng qua các cổng vào phòng.

Dữ liệu vào

Dòng đầu tiên của tệp vào chứa ba số nguyên $a,b,c$ giới hạn kích thước giường. Một trong các kích thước (chiều dài, chiều rộng và chiều cao) không được vượt quá $a$, một kích thước khác không được vượt quá $b$, và kích thước còn lại không được vượt quá $c$ ($1\le a,b,c\le 500$).

Dòng tiếp theo chứa một số nguyên $n$ — số cổng trên hành tinh ($2\le n\le 500$). Các cổng được đánh số từ $1$ đến $n$. Cổng ở cửa hàng có số $1$, còn cổng dẫn đến phòng của Basilius có số $n$.

Tiếp theo là $n$ dòng của tệp vào mô tả các cổng Nibiru, mỗi dòng một cổng. Dòng thứ $i$ mô tả cổng thứ $i$ và bắt đầu bằng ba số thực cách nhau bởi dấu cách: $w_i,h_i,k_i$. Hai số đầu xác định chiều rộng và chiều cao của cổng, còn số thứ ba là số cổng có thể đến trực tiếp bằng cách đi qua cổng đang được mô tả ($1\le w_i,h_i\le 300$, $0\le k_i<n$). Sau đó là $k_i$ số nguyên đôi một khác nhau $p_{ij}$: chúng là số hiệu các cổng có thể đến trực tiếp từ cổng thứ $i$ ($1\le p_{ij}\le n$, $p_{ij}\ne i$).

Dữ liệu ra

Tệp ra phải chứa ba số nguyên dương $x,y,z$ theo thứ tự bất kỳ — kích thước chiếc giường có thể tích lớn nhất mà Basilius có thể mang từ cửa hàng đến phòng ký túc xá. Nếu có nhiều phương án có thể tích lớn nhất, hãy in ra phương án bất kỳ. Đảm bảo rằng bài toán có lời giải.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

100 200 300

Dữ liệu vào 2

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

Dữ liệu ra 2

200 300 300