Construct Matrix
Contest: Codeforces Round 917 (Div. 2)
Difficulty rating: 2500
Tags: constructive algorithms, math

You are given an even integer $$$n$$$ and an integer $$$k$$$. Your task is to construct a matrix of size $$$n \times n$$$ consisting of numbers $$$0$$$ and $$$1$$$ in such a way that the following conditions are true, or report that it is impossible:

- the sum of all the numbers in the matrix is exactly $$$k$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the row $$$i$$$ is the same for each $$$i$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the column $$$j$$$ is the same for each $$$j$$$.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 130$$$) — the number of test cases. The description of the test cases follows.

Each test case is described by a single line, which contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 1000$$$, $$$n$$$ is even, $$$0 \leq k \leq n^2$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output format:
For each test case, output $$$\texttt{Yes}$$$ if it's possible to construct a matrix that satisfies all of the problem's conditions, and $$$\texttt{No}$$$ otherwise.

If it is possible to construct a matrix, the $$$i$$$-th of the next $$$n$$$ lines should contain $$$n$$$ integers representing the elements in the $$$i$$$-th row of the matrix.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, all conditions are satisfied:

- the sum of all the numbers in the matrix is exactly $$$0$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the row $$$i$$$ is $$$0$$$ for each $$$i$$$;
- the bitwise $$$\texttt{XOR}$$$ of all the numbers in the column $$$j$$$ is $$$0$$$ for each $$$j$$$.

In the third example, it can be shown that it's impossible to find a matrix satisfying all the problem's conditions.

Example input:
5
4 0
6 6
6 5
4 2
6 36

Example output:
Yes
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Yes
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
No
No
Yes
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

Editorial:
Hint $$$1$$$: Does solution exist when $$$k$$$ is odd?
Hint $$$2$$$: What can you understand when $$$k = 2$$$ or $$$k = n^2 - 2$$$?
Hint $$$3$$$: How can we easily fill the matrix with $$$1$$$s, such that all problem conditions are satisfied when $$$k$$$ is divisible by $$$4$$$?
Hint $$$4$$$: How will you solve the problem when $$$k = 6$$$?
Hint $$$5$$$: Try to merge ideas of Hint $$$3$$$ and Hint $$$4$$$ together.
Editorial:
First, let's note that when $$$k$$$ is odd, the solution doesn't exist. It's obvious since in the solution the xors of all the rows are the same, it follows that the parity of the number of $$$1$$$s in each row is the same, and let's remember that $$$n$$$ is even, and from these conditions get that solution exists only when $$$k$$$ is even.
Second, let's note that for $$$k = 2$$$ or $$$k = n^2 - 2$$$, the solution exists only for $$$n = 2$$$.
For all other cases, a solution always exists.
• when $$$k \equiv 0 \pmod{4}$$$, we can fill $$$\frac{k}{4}$$$ submatrices of size $$$2 \times 2$$$.
• when $$$k \equiv 2 \pmod{4}$$$. Let's note that $$$k \geq 6$$$. Let's write $$$1$$$ in the following positions: $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$. After this, we should fill the remaining $$$(k - 6)$$$ $$$1$$$s, and let's note that $$$(k - 6) \equiv 0 \pmod{4}$$$. There are obvious $$$\frac{(n^2 - 16)}{4}$$$ submatrices of size $$$2 \times 2$$$, which aren't filled yet — outside the top left $$$4 \times 4$$$ submatrix. If $$$k < n^2 - 6$$$, then we can fill as many of those $$$2 \times 2$$$ submatrices as necessary, otherwise if $$$k = n^2 - 6$$$, we can also fill with $$$1$$$s the following $$$4$$$ positions too: $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(4, 3)$$$, $$$(4, 4)$$$.