L :: Another Brick in the Wall
Time Limit: 3 Seconds Memory Limit: 65536 KB
Special Judge
The Russia fiasco has finally caught up to Donald Trump and led to his impeachment. Looking for a job that suits an incompetent manager, he has landed himself a position as the head of the ECE department at the University of Tehran. The first item on his agenda is building a wall to keep undesirable students from other, lesser universities out. He has enlisted your help in accomplishing this task. Donald has an (a x b) wall in mind and you have an unlimited supply of (1 x 2) sized bricks at your disposal to build it.
Donald wants the wall to be strong; a wall is strong if and only if every line that goes between two consecutive rows or columns crosses at least one brick, i.e. if there is a line going between two successive rows or columns that only goes through the mortar between the bricks the wall is not strong.
For example the following wall is not strong because of the highlighted line:
A (3 x 4) wall that is not strong.
Input
The first line of the input contains a single number (T ≤ 100) denoting the number of test cases. Each of the T following lines consists of two numbers (4 < a, b ≤ 3000) denoting the size of the wall.
Output
For every test case your program must output an (a x b) table of integers indicating the placement of the bricks in the wall. Every brick is identified by a number between zero (inclusive) and the total number of bricks used (exclusive). If building a strong wall of the given size is impossible, output a single line containing the string "Impossible".
Sample Input
2 5 6 5 5
Sample Output
0 1 1 2 3 3 0 4 4 2 5 6 7 8 9 9 5 6 7 8 11 12 12 14 10 10 11 13 13 14 ImpossibleSubmit
Source: 15th Iran Nationwide Internet Contest