Description

Given positive integers $n, m$, with the guarantee that $m$ is even.

There is a robot in an $n \times m$ non-negative integer matrix $A$. The rows are numbered $1 \sim n$, and the columns are numbered $1 \sim m$. Let the current position of the robot be $(x, y)$, initially $(x, y) = (1, 1)$. The robot cyclically performs the following operations:

1. Move to $y-1$ or $y+1$ or do not move (it must not move outside the matrix).
2. Move down one step. If this move goes beyond the matrix size, the loop stops.

Your task is to construct an $n \times m$ matrix $A$, where each row of the matrix contains exactly $\frac{m}{2}$ zeros and $\frac{m}{2}$ ones, such that the sum of all $A_{i,j}$ that the robot passes through is minimized. The robot is infinitely smart and will choose the route that maximizes the sum of $A_{i,j}$ it passes through. Note that the initial position is also considered as passed by the robot. If there are multiple optimal solutions, you may output any one of them.

Input Format

One line containing two positive integers $n, m$, with the guarantee that $m$ is even.

Output Format

Output $n$ lines, each containing $m$ non-negative integers (either $0$ or $1$), representing the constructed matrix.

This problem uses a custom checker. If there are multiple solutions, output any valid one.

2 4

0 0 1 1
0 0 1 1

Hint

【Sample Explanation】

For the first sample, the optimal path for the robot is:

1. Start at $(1,1)$, $A_{1,1}=0$;
2. Move to $(1,2)$, $A_{1,2}=0$;
3. Move to $(2,2)$, $A_{2,2}=0$;
4. Move to $(2,3)$, $A_{2,3}=1$.

The total sum of $A_{i,j}$ values that the robot passes through is $1$. Clearly, no better construction exists.

【Data Range】

This problem uses bundled testing.

For all test cases, $2 \le n, m \le 5 \times 10^3$, and $m$ is even.

Translated by DeepSeek V3.1