Đề bài

Ngày thi đầu tiên đầy hỗn loạn đã kết thúc. Dù Ủy ban Khoa học vừa kịp ngăn cuộc tấn công vào máy chủ chấm bài, họ lo rằng việc chấm các bài nộp đã bị ảnh hưởng. Chỉ còn một cách: chấm lại tất cả bài nộp.

Máy chủ có \(N\) lõi xử lý. Ủy ban đã gán cho mỗi lõi một danh sách gồm \(S\) bài nộp; mỗi bài thuộc một trong \(T\) bài toán, được đánh số từ \(1\) đến \(T\). Giá trị \(S\) là một lũy thừa dương của \(2\). Trong \(S\) phút tiếp theo, mỗi lõi sẽ chấm đúng một bài trong danh sách của nó ở mỗi phút.

Cơ sở dữ liệu chứa dữ liệu đề khá mong manh và có thể sập nếu số yêu cầu đồng thời cho dữ liệu của cùng một bài biến động quá nhiều. Vì vậy, Ủy ban muốn sắp thứ tự các bài nộp trên từng lõi sao cho trong suốt quá trình chấm lại, đối với mỗi bài toán, chênh lệch giữa số bài nộp được chấm đồng thời lớn nhất và nhỏ nhất không quá \(1\).

Hãy tính một cách sắp thứ tự thỏa mãn yêu cầu.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(N\), \(S\) và \(T\).

Mỗi trong \(N\) dòng tiếp theo mô tả danh sách bài nộp đã gán cho một lõi. Dòng thứ \(i\) chứa \(S\) số nguyên \(t_1,t_2,\ldots,t_S\) (\(1\le t_j\le T\)), cho biết lõi thứ \(i\) được gán các bài nộp thuộc những bài toán đó.

Dữ liệu ra

In \(N\) dòng mô tả một cách sắp thứ tự hợp lệ. Dòng thứ \(i\) chứa \(S\) số nguyên \(r_1,r_2,\ldots,r_S\); lõi thứ \(i\) sẽ chấm một bài thuộc bài toán \(r_j\) trong phút thứ \(j\).

Với mỗi lõi, dãy được in phải là một hoán vị của danh sách bài toán trên dòng tương ứng của dữ liệu vào. Đối với mỗi bài toán, chênh lệch giữa số bài nộp thuộc bài đó được chấm đồng thời lớn nhất và nhỏ nhất qua \(S\) phút phải không quá \(1\).

Dữ liệu bảo đảm luôn tồn tại ít nhất một cách sắp hợp lệ.

Ràng buộc

• \(S=2^k\) với một số nguyên dương \(k\).
• \(1\le N,S,T\le 100\,000\).
• \(N\cdot S\le 500\,000\).

Phân nhóm

• Subtask 1 (10 điểm): \(S=2\) và \(N,T\le20\).
• Subtask 2 (25 điểm): \(S=2\). Subtask gồm ba nhóm lần lượt trị giá \(15\), \(5\) và \(5\) điểm.
• Subtask 3 (25 điểm): \(N\cdot S\le10\,000\). Subtask gồm ba nhóm lần lượt trị giá \(15\), \(5\) và \(5\) điểm.
• Subtask 4 (40 điểm): Không có ràng buộc bổ sung. Subtask gồm ba nhóm lần lượt trị giá \(20\), \(10\) và \(10\) điểm.

Trong các Subtask 2, 3 và 4:

• Nhóm 1: \(T\le N\) và tổng số bài nộp của mỗi bài toán chia hết cho \(S\).
• Nhóm 2: \(T\le N\), không còn yêu cầu chia hết. Điểm nhóm này được cộng thêm vào Nhóm 1.
• Nhóm 3: Không có ràng buộc bổ sung. Điểm nhóm này được cộng thêm vào hai nhóm trước.

Ví dụ

3 2 3
1 2
2 3
2 3

2 1
3 2
2 3

3 4 3
2 3 2 2
2 3 3 2
2 2 3 2

2 2 2 3
3 2 3 2
2 3 2 2