ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1596. Knight Mare

Time limit: 5.0 second
Memory limit: 64 MB
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.

Input

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.

Output

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.
  1. (2, 1)
  2. (2, −1)
  3. (−2, 1)
  4. (−2, −1)
  5. (1, 2)
  6. (1, −2)
  7. (−1, 2)
  8. (−1, −2)
Topleft cell's coordinates are (1, 1).

Samples

inputoutput
6 7
5 1 5 6 2 6 2 
7 2 6 8 7 8 8 
1 4 8 6 7 6 4 
1 2 6 1 1 6 4 
5 5 4 3 5 3 8 
7 3 7 7 7 3 4 
7 7
No solution
Problem Author: Vladimir Basunkov