
ZOJ Problem Set  3966
Chiaki has an n × m rectangular chessboard. She would like to tile this board with dominoes, where a domino is a 2 × 1 rectangle, such that:
The figure below shows some forbidden configurations: The figure below shows two valid tilings of 4 × 4 chessboard: You also need to number the dominoes of chessboard so that no two dominoes have the same number. You can use the number from 1 to n × m. InputThere are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case: The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the size of the rectangular chessboard. It is guaranteed that the sum of n × m over all test cases does not exceed 2 × 10^{6}. OutputFor each test case, output a valid chessboard described above. A valid chessboard consists of n lines and each line contains m integers. Each integer in the output should represent the id of a domino. The grids sharing the same id belong to the same domino. If there is no solution, output "Impossible!" (without the quotes) instead. Sample Input3 1 1 4 3 4 4 Sample OutputImpossible! 1 1 2 3 4 2 3 4 5 6 6 5 1 1 2 2 3 4 4 5 3 6 6 5 7 7 8 8 Author: LIN, Xi Source: The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 