When JediKittens are finishing their training and are ready to become JediCat, they are presented with another mind challenge. This challenge is a bit harder, despite the rules of it being very simple. Every soon-to-be-JediCat is given an N × M chessboard and one white knight. The task is simple — using the knight, moving it according to usual rules, the JediKittens are to visit every cell of the board exactly once, and after that return to the starting cell (this is the only cell, which is visited twice). JediKittens can cope with this task, can you?

We should remind, that usual move of a chess knight is a shift two cells in one direction, and then one cell in perpendicular direction.

The first line contains integers N and M that are the size of chessboard (6 ≤ N, M ≤ 1000). Chessboard is M cells width and N cells height.

If there is no solution just print “No solution” without quotes. Otherwise print N lines with M integers. Each integer should be from 1 to 8, which means in what direction there will be the next step of knight's tour from cell (i, j) performed. Here is the array of 8 directions.

Topleft cell's coordinates are (1, 1).