Problem Description

Given a $n \times n$ rectangle, there are obstacles in $k$ consecutive grid cells starting from the top-left corner along the diagonal. You can place several $1 \times 2$ small rectangles into this large rectangle, with the condition that no two small rectangles occupy the same grid cell and they must not touch the obstacles. For example, the following diagram shows an example for $n=4, k=2$ where we have placed 6 $1 \times 2$ small rectangles.

Given $n, k$, please output a scheme that places as many $1 \times 2$ small rectangles as possible. It can be proven that for $n=4, k=2$, at most 6 small rectangles can be placed.

Input Format

Input consists of two positive integers $n, k$ separated by a space, representing the size of the rectangle and the number of obstacles.

Output Format

Output $n$ lines, each containing $n$ integers (separated by any number of spaces). The placed small rectangles are numbered as $1, 2, \cdots$. Grid cells without a small rectangle are output as $0$. If there are multiple optimal solutions (placing the maximum number of small rectangles), output any one of them.

Sample Input and Output

Sample Input #1

4 2

Sample Output #1

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

Sample Input #2

5 3

Sample Output #2

0 8 8 9 10
1 0 0 9 10
1 3 0 0 7
2 3 5 5 7
2 4 4 6 6

Notes

For $50\%$ of the test cases, $1 \le k \le n \le 10$.

For $100\%$ of the test cases, $1 \le k \le n \le 50$.

This problem originally had a maximum score of $20\text{pts}$.

见题面 Input 部分

见题面 Output 部分