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, ..., n~) và món quà ~j~ (~j = 1, 2, ..., 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, ..., 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, ..., 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.

Input

• Dòng đầu tiên ghi số nguyên dương ~n, m~ (~n \le m~);
• Dòng thứ ~i~ (~i = 1, 2, ..., n~) trong ~n~ dòng tiếp theo chứa ~m~ số nguyên dương ~s_{i1}, s_{i2}, ..., 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, ..., 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.

Sample Input 1

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

Sample Output 1

2 4 5
3 1 2 3

Giải thích: Theo phương án trên, bạn thứ nhất nhận hai món quà có chỉ số 4 và 5, bạn thứ hai nhận ba món quà có chỉ số 1, 2, 3. Khi đó ~r_1 = 4 + 5 = 9, r_2 = 3 + 3 + 4 = 9~ và ~w = \min \{9, 9\} = 9~. Nếu ~w_p = 9~ thì em sẽ được ~1000 \times \frac{1000 \times 9 - 999 \times 9}{9} = 1~ điểm.

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~.

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 ~\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.