310987: CF1917E. Construct Matrix

E. Construct Matrixtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExampleInput

5
4 0
6 6
6 5
4 2
6 36

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

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.

题目大意：
给定一个偶数n和一个整数k，构造一个n×n的矩阵，矩阵由0和1组成，需满足以下条件，或者报告无法构造：
- 矩阵中所有数字之和正好是k；
- 每一行的按位异或（XOR）结果相同；
- 每一列的按位异或结果也相同。

输入数据格式：
每个测试包含多个测试案例。第一行是一个整数t（1≤t≤130）——测试案例的数量。接下来是每个测试案例的描述。
每个测试案例由一行组成，包含两个整数n和k（2≤n≤1000，n是偶数，0≤k≤n²）。
保证所有测试案例中n的总和不超过2000。

输出数据格式：
对于每个测试案例，如果可以构造一个满足所有条件的矩阵，输出"Yes"，否则输出"No"。
如果可以构造矩阵，接下来的n行应该包含n个整数，代表矩阵的第i行元素。

示例：
输入：
```
5
4 0
6 6
6 5
4 2
6 36
```
输出：
```
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
```

注意：
在第一个示例中，所有条件都得到满足：
- 矩阵中所有数字之和正好是0；
- 每一行的按位异或结果都是0；
- 每一列的按位异或结果也都是0。

在第三个示例中，可以证明不可能找到一个满足所有条件的矩阵。题目大意： 给定一个偶数n和一个整数k，构造一个n×n的矩阵，矩阵由0和1组成，需满足以下条件，或者报告无法构造： - 矩阵中所有数字之和正好是k； - 每一行的按位异或（XOR）结果相同； - 每一列的按位异或结果也相同。 输入数据格式： 每个测试包含多个测试案例。第一行是一个整数t（1≤t≤130）——测试案例的数量。接下来是每个测试案例的描述。 每个测试案例由一行组成，包含两个整数n和k（2≤n≤1000，n是偶数，0≤k≤n²）。 保证所有测试案例中n的总和不超过2000。 输出数据格式： 对于每个测试案例，如果可以构造一个满足所有条件的矩阵，输出"Yes"，否则输出"No"。 如果可以构造矩阵，接下来的n行应该包含n个整数，代表矩阵的第i行元素。 示例： 输入： ``` 5 4 0 6 6 6 5 4 2 6 36 ``` 输出： ``` 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 ``` 注意： 在第一个示例中，所有条件都得到满足： - 矩阵中所有数字之和正好是0； - 每一行的按位异或结果都是0； - 每一列的按位异或结果也都是0。 在第三个示例中，可以证明不可能找到一个满足所有条件的矩阵。