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 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,\cdots,n)\) và món quà \(j (j=1,2,\cdots,m)\) thầy Phương có thông tin \(s_{i_j}\) 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,\cdots,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,\cdots,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_{i_j}\), 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.

Input

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

Output

• Ghi ra \(n\) dòng, dòng thứ \(i (i=1,2,\cdots,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.
    Tính đ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), \(w\) giá trị theo phương án của em, khi đó em sẽ nhận được \(\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. Khác với kỳ thi chính thức, các bạn sẽ được bonus nếu đáp án lớn hơn đáp án của thầy.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m,n \leq 12\);
• Subtask \(2\) (\(40\%\) số điểm): \(m \leq 1200,n=2\);
• Subtask \(3\) (\(30\%\) số điểm): \(m=n \leq 1200\)

Example

2 5
1 2 3 4 5
3 3 4 2 1 

2 4 5
3 1 2 3