Khi quân đội của Trung sĩ Argus tập hợp để luyện tập, họ đứng thành lưới vuông \(N\times N\), mỗi ô đúng một binh sĩ. Mỗi người có một chiều cao.

Argus muốn luôn quan sát được mọi binh sĩ. Vì thích nhìn lưới từ góc trên trái, ông yêu cầu:

• trong mỗi hàng, chiều cao tăng nghiêm ngặt từ trái sang phải;
• trong mỗi cột, chiều cao tăng nghiêm ngặt từ trên xuống dưới.

Hai binh sĩ trong cùng hàng hoặc cột không thể cao bằng nhau, nhưng nhiều binh sĩ ở các vị trí khác trong lưới vẫn có thể cùng chiều cao.

Vì đôi lúc binh sĩ luyện riêng theo hàng hoặc cột, Argus yêu cầu báo cáo gồm \(2N\) danh sách chiều cao: mỗi hàng theo thứ tự trái sang phải và mỗi cột theo thứ tự trên xuống dưới. Bạn ghi từng danh sách lên một mảnh giấy riêng. Trên đường về văn phòng, tiếng kèn lớn làm bạn giật mình đánh rơi giấy; gió cuốn mất một mảnh trước khi bạn nhặt lại. Các mảnh còn lại không theo thứ tự, và bạn cũng quên mảnh nào là hàng hay cột vì không ghi chú.

Argus sẽ bắt bạn chống đẩy hàng trăm lần nếu báo cáo thiếu. Hãy tìm danh sách bị mất.

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm một dòng chứa \(N\), sau đó là \(2N-1\) dòng, mỗi dòng có \(N\) số nguyên biểu diễn các danh sách còn lại. Bảo đảm chúng là tất cả trừ một hàng hoặc cột của một lưới hợp lệ như mô tả.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là \(N\) số nguyên tăng nghiêm ngặt của danh sách bị thiếu.

Ràng buộc

• \(1\le T\le50\).
• Mọi chiều cao nằm trong \([1,2500]\).
• Các số trên mỗi dòng tăng nghiêm ngặt.
• Bảo đảm tồn tại duy nhất một đáp án hợp lệ.

Phân nhóm

• Test Set 1 (Visible): \(2\le N\le10\).
• Test Set 2 (Hidden): \(2\le N\le50\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Case #1: 3 4 6

1 2 3
2 3 4
3 5 6

1 2 3
2 3 5
3 4 6

Nguồn

Google Code Jam 2016, Vòng 1A, bài Rank and File.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.