Một lớp học nọ có ~n~ học sinh. Thầy giáo cho họ một túi kẹo ~U~ có ~m~ viên kẹo được đánh số từ ~1~ đến ~m~. Với học sinh ~i~, viên kẹo thứ ~k~ có độ ngon là ~v_i(k)~. Tương tự, một túi kẹo nhỏ bất kỳ ~S~ lấy từ ~U~ có độ ngon là tổng độ ngon (đối với học sinh ~i~) của các viên kẹo có trong túi ~S~.

Là một học sinh ưu tú của lớp học đề cao thực lực, bạn cần chia túi kẹo ~U~ thành ~n~ túi kẹo nhỏ ~S_1, S_2, \dots, S_n~ (học sinh ~i~ sẽ nhận túi ~S_i~) sao cho:

• Một viên kẹo phải được nằm trong duy nhất một túi nào đó.
• Mỗi túi phải có ít nhất ~1~ viên kẹo.
• Với mỗi học sinh ~i~, bạn ấy không muốn túi kẹo ~S_i~ của mình quá tệ so với những túi kẹo khác. Chi tiết hơn, bạn cần phải đảm bảo ~v_i(S_i) \ge v_i(S_j) - \max_{k \in S_j} v_i(k)~ với mọi ~i, j~ ~(1 \le i, j \le n, i \neq j)~.

Ta có thể chứng minh được là luôn có cách chia kẹo để thỏa mãn các điều kiện trên. Hãy tìm và in ra một cách chia kẹo như thế.

Input

• Dòng đầu tiên chứa ~2~ số nguyên dương ~n~ và ~m~ ~(1 \le n \le m \le 500)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên ~v_i(1), v_i(2), \dots, v_i(m)~ ~(0 \le v_i(j) \le 10^9)~ tương ứng với độ ngon của ~m~ viên kẹo với học sinh ~i~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ chứa số nguyên ~k_i~ là số lượng kẹo của túi ~S_i~, tiếp đến là ~k_i~ số nguyên ngăn cách bởi dấu cách tương ứng là chỉ số của những viên kẹo trong túi ~S_i~.

Subtask

• Có ~10\%~ số test là ~m = n~.
• Có ~10\%~ số test là ~n = 2~.
• Còn lại không có ràng buộc gì thêm.

Sample Input

4 4
34 8 8 25
4 30 2 8
32 32 28 35
28 17 18 0

Sample Output

1 1
1 2
1 4
1 3