Phần thưởng

Vào ngày 19 tháng 5, là ngày sinh nhật Bác, thầy Phương sẽ tổ chức một buổi liên hoan và tặng thưởng cho các bạn có nhiều tiến bộ khi tham gia HCC. Có $n$ bạn được mọi người đánh giá cao, các bạn này sẽ được nhận quà của thầy Phương. Thầy Phương đã chuẩn bị $m$ món quà, đồng thời thu thập thông tin mong muốn nhận quà của từng bạn. Các bạn được đánh số từ $1$ đến $n$, các món quà được đánh số từ $1$ đến $m$, với bạn thứ $i$ ($i=1,2,\dots ,n$) và món quà $j$ ($j=1,2,\dots ,m$) thầy Phương có thông tin $s_{ij}$ là một số nguyên dương đánh giá nguyện vọng của bạn $i$ muốn nhận món quà $j$.

Mỗi một món quà sẽ được tặng cho đúng một bạn, mỗi bạn sẽ được nhận ít nhất một món quà. Gọi $r_i$ ($i=1,2,\dots ,n$) là tổng đánh giá nguyện vọng của các món quà mà người $i$ nhận được và $w=min\{r_1,r_2,\dots ,r_n\}$. Thầy Phương muốn tìm cách tặng quà để giá trị $w$ đạt giá trị càng lớn càng tốt.

Yêu cầu: Cho $n,m$ và các giá trị $s_{ij}$, em hãy giúp thầy Phương tìm phương án tặng quà để giá trị $w$ đạt giá trị càng lớn càng tốt.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $n,m$ ($n\le m$);
• Dòng thứ $i$ ($i=1,2,\dots ,n$) trong $n$ dòng tiếp theo chứa $m$ số nguyên dương $s_{i1},s_{i2},\dots ,s_{im}$. Các số có giá trị không vượt quá $1000$.

Dữ liệu ra

In ra $n$ dòng, dòng thứ $i$ ($i=1,2,\dots ,n$) có dạng:

• Số đầu tiên ghi số $p_i$ là số món quà mà bạn $i$ nhận được;
• Tiếp theo là $p_i$ số là chỉ số những món quà mà bạn $i$ được nhận. Các chỉ số được liệt kê theo thứ tự tăng dần.

Mỗi món quà phải xuất hiện ở đúng một dòng và $p_i\ge 1$ với mọi $i$. Nếu có nhiều phương án, in ra một phương án bất kỳ.

Ràng buộc

• $1\le n\le m$.
• $1\le s_{ij}\le 1000$.
• Mọi test thỏa mãn một trong ba điều kiện của phần Subtasks; nói riêng $m\le 1200$.

Subtasks

• Có $30\%$ số lượng test ứng với $30\%$ số điểm thỏa mãn điều kiện: $m,n\le 12$;
• Có $40\%$ số lượng test khác ứng với $40\%$ số điểm thỏa mãn điều kiện: $m\le 1200$, $n=2$;
• Có $30\%$ số lượng test còn lại ứng với $30\%$ số điểm thỏa mãn điều kiện: $m=n\le 1200$.

Chấm điểm

Với mỗi test, gọi $w_P$ là giá trị theo phương án mà thầy Phương tìm được (giá trị này em không được biết, chỉ dùng khi chấm; phương án của thầy Phương là tối ưu), $w$ là giá trị theo phương án của em, khi đó em sẽ nhận được $min\{1,\frac{1000\times w-999\times w_P}{w_P}\}$ trên tổng số $1$ điểm của test đó; nếu $1000\times w<999\times w_P$ em sẽ nhận $0$ điểm. Phương án không hợp lệ được $0$ điểm.

Ví dụ