Indicium trong tiếng Latinh có nghĩa là "vết" (trace). Trong bài này, chúng ta làm việc với các hình vuông Latinh và vết của ma trận.

Một hình vuông Latinh là ma trận vuông \(N\times N\), trong đó mỗi ô chứa một trong \(N\) giá trị khác nhau và không giá trị nào lặp lại trong cùng một hàng hoặc cột. Bài này chỉ xét các "hình vuông Latinh tự nhiên", tức là \(N\) giá trị được dùng là các số nguyên từ \(1\) đến \(N\).

Vết của ma trận vuông là tổng các giá trị trên đường chéo chính (từ góc trên bên trái đến góc dưới bên phải).

Cho \(N\) và \(K\), hãy tạo một hình vuông Latinh tự nhiên \(N\times N\) có vết \(K\), hoặc cho biết điều đó là không thể. Ví dụ, dưới đây là hai đáp án có thể có với \(N=3\), \(K=6\); các giá trị góp vào vết được in đậm.

**2** 1 3     **3** 1 2
3 **2** 1     1 **2** 3
1 3 **2**     2 3 **1**

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test, mỗi bộ gồm một dòng chứa hai số nguyên \(N\) và \(K\): kích thước ma trận và vết mong muốn.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn y là IMPOSSIBLE nếu không có đáp án hoặc POSSIBLE nếu có. Trong trường hợp thứ hai, in thêm \(N\) dòng, mỗi dòng gồm \(N\) số nguyên, biểu diễn một hình vuông Latinh tự nhiên hợp lệ có vết \(K\).

Ràng buộc

• \(N \le K \le N^2\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(T=44\); \(2 \le N \le 5\).
• Test Set 2 (phán quyết ẩn): \(1 \le T \le 100\); \(2 \le N \le 50\).

Đ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ụ

2
3 6
2 3

Case #1: POSSIBLE
2 1 3
3 2 1
1 3 2
Case #2: IMPOSSIBLE

1 2     2 1
2 1     1 2

Nguồn

Google Code Jam 2020, Vòng loại, bài Indicium.

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