Percy is a student studying at Heung Shing Secondary School. On the ground floor of the school, there is a piece of land for building a carpark. The piece of land can be represented by a grid with $$$N$$$ rows and $$$M$$$ columns. The land is surrounded by roads on all 4 sides. One day, the school principal asks Percy to redesign the carpark's layout.
A parking spot requires 2 connected cells, i.e. a vertical or horizontal $$$1 \times 2$$$ region. Parking spots that touch the boundary of the land can be directly accessed by the external roads. Cells that are not part of a parking spot form the internal roads. A parking spot is also accessible if it is possible to reach the boundary of the land from the parking spot via some internal roads.
The principal has decided to give the Student of the Year award to Percy if he manages to design a layout that meets all of the following criteria:
For example, in the layout below, the parking spots are all accessible by external and internal roads and the total area is $$$30 / 36 \approx 83.3\%$$$. Therefore it is an acceptable layout.
As a friend of Percy, can you help him to win the Student of the Year award?
The input contains only one line with two integers, $$$N$$$ and $$$M$$$ ($$$2 \leq N, M \leq 100$$$).
The output should contain $$$N$$$ lines, each of which contains $$$M$$$ integers separated by spaces, representing the layout of the carpark.
For the cells that are not part of a parking spot, you should use the integer $$$0$$$ to represent them.
For each parking spot, you should use a unique positive integer between $$$1$$$ and $$$2^{31} - 1$$$ to represent it. So for each positive integer between $$$1$$$ and $$$2^{31} - 1$$$, it should only appear 0 or 2 times in the output.
It can be shown that a solution always exist with the given constraints.
4 9
1 1 0 3 4 5 0 2 2 6 7 0 3 4 5 0 8 9 6 7 10 10 0 11 11 8 9 12 12 13 13 0 14 14 15 15
