P13052 [GCJ 2020 Qualification] Indicium

Indicium means "trace" in Latin. In this problem we work with Latin squares and matrix traces. A Latin square is an $\mathbf{N}$-by-$\mathbf{N}$ square matrix in which each cell contains one of $\mathbf{N}$ different values, such that no value is repeated within a row or a column. In this problem, we will deal only with "natural Latin squares" in which the $\mathbf{N}$ values are the integers between 1 and $\mathbf{N}$. The trace of a square matrix is the sum of the values on the main diagonal (which runs from the upper left to the lower right). Given values $\mathbf{N}$ and $\mathbf{K}$, produce any $\mathbf{N}$-by-$\mathbf{N}$ "natural Latin square" with trace $\mathbf{K}$, or say it is impossible. For example, here are two possible answers for $\mathbf{N}=3, \mathbf{K}=6$. In each case, the values that contribute to the trace are underlined. $\begin{array}{llll}\underline{2} & 1 & 3 & \underline{3} \\3 & \underline{2} & 1 & 1 \\1 & 3 & \underline{2} & 2\end{array} \begin{array}{lll}1 & 2 \\ \underline{2} & 3 \\3 & \underline{1}\end{array}$

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each consists of one line containing two integers $\mathbf{N}$ and $\mathbf{K}$ : the desired size of the matrix and the desired trace.

For each test case, output one line containing `Case #x: y`, where $x$ is the test case number (starting from 1) and $y$ is IMPOSSIBLE if there is no answer for the given parameters or POSSIBLE otherwise. In the latter case, output $\mathbf{N}$ more lines of $\mathbf{N}$ integers each, representing a valid "natural Latin square" with a trace of $\mathbf{K}$, as described above.

**Sample Explanation** Sample Case #1 is the one described in the problem statement. Sample Case #2 has no answer. The only possible 2-by-2 "natural Latin squares" are as follows: ``` 1 2 2 1 2 1 1 2 ``` These have traces of 2 and 4, respectively. There is no way to get a trace of 3. **Limits** - $\mathrm{N} \leqslant \mathrm{K} \leqslant \mathrm{N}^{2}$. **Test set 1 (7 Pts, Visible Verdict)** - $\mathrm{T}=44$. - $2 \leqslant \mathrm{N} \leqslant 5$. **Test set 2 (25 Pts, Hidden Verdict)** - $1 \leqslant \mathrm{T} \leqslant 100$. - $2 \leqslant \mathrm{N} \leqslant 50$.