J. Cereal Grids III (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Allen is tired of playing with alphabet cereal, so he found some binary cereal to play with instead! Allen has $$$n^2$$$ pieces of cereal, each with number $$$0$$$ or $$$1$$$.

This time, Allen is trying to place cereal in an $$$n$$$ x $$$n$$$ grid of cells in order to minimize the grid's Super Rank .

The Super Rank is defined as the number of distinct rows and columns (if the rows were read from left to right, and columns were read from top to bottom).

For example, the binary grid:

$$$1$$$$$$1$$$$$$1$$$
$$$1$$$$$$0$$$$$$0$$$
$$$1$$$$$$0$$$$$$0$$$

Has a super rank of $$$2$$$, since the rows and columns are all $$$111$$$ or $$$100$$$.

Given that Allen has $$$k$$$ pieces of $$$1$$$ cereal and $$$n^2 - k$$$ pieces of $$$0$$$ cereal, output any grid that minimizes the Super Rank.

Input

The first line contains two space seperated integers: $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 1000$$$, $$$0 \leq k \leq n^2$$$)

Output

Output $$$N$$$ lines, with the $$$i$$$th line being a binary string representing the $$$i$$$th row on the grid.

Examples
Input
5 8
Output
10001
00010
00010
01100
10001
Input
3 5
Output
111
100
100
Note

In test case 1, the super rank is 3; the distinct rows and columns are: "$$$10001$$$", "$$$00010$$$", and "$$$01100$$$". It can be proven that this is the minimum super rank.