Colored Domino Tilings and Cuts

Problem code: DOMNOCUT

All submissions for this problem are available.

Consider rectangular grid that composed of N rows and M columns. Colored domino tiling of the grid is some way to put lowercase English letter in each cell of the grid provided that each cell has exactly one neighbor with the same letter as in this cell. Two cells of the grid are neighbors if they share a common side. Each letter represents some color. Cut of colored domino tiling is vertical or horizontal line that divides the grid in two colored domino tilings. In other words this line should not pass between two adjacent cells with the same color.

For given N and M you should find the colored domino tiling that has the minimal possible number of cuts. If there are several solutions you should find among them the tiling that uses the minimal possible number of colors in it. If your tiling requires K colors then use first K lowercase letters of English alphabet as colors. If there are still several solutions then find any such tiling.

Input

The first line contains a positive integer T, the number of test cases. In the following lines, T test cases follow. Every test case is a single line that contains two space separated positive integers, N and M, the sizes of the grid.

Output

For each test case output in the first line the word "IMPOSSIBLE" without quotes if there are no tilings of the grid with N rows and M columns. Otherwise output in the first line two space separated integers, the minimal number of cuts and minimal number of colors in required tiling and then in the next N lines output the tiling itself. Each of these N lines must be composed of exactly M lowercase English letters.

Constraints

1 <= T <= 3000
1 <= N, M <= 500
sum of N*M in the file <= 2,000,000

Sample input

5
1 1
2 2
2 3
4 3
5 5

Sample output

IMPOSSIBLE
1 2
ab
ab
1 3
aab
ccb
1 3
aab
ccb
baa
bcc
IMPOSSIBLE
Author: anton_lunyov
Tester: chmel_tolstiy
Editorial http://discuss.codechef.com/problems/DOMNOCUT
Date Added: 23-07-2011
Time Limit: 4 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

1) "Cut of colored domino

jughead @ 1 Nov 2011 04:05 PM
1) "Cut of colored domino tiling is vertical or horizontal line that divides the grid in two [strong]colored domino tilings[/strong]". 2) "In other words this line should not pass between two adjacent cells with the same color." According to the definition of Colored domino tiling this two sentences are not equal.

@Admin: I think there has

rushilpaul @ 6 Nov 2011 04:26 PM
@Admin: I think there has been a mistake in the last test case for 5 5. the output should be: 1 3 aaaab aaaab aaaab aaaab ccccc

Unfortunately the new lines

rushilpaul @ 6 Nov 2011 04:28 PM
Unfortunately the new lines chars have been ignored. Each of those strings are on newlines.

Oh, my mistake! Overlooked

rushilpaul @ 6 Nov 2011 04:30 PM
Oh, my mistake! Overlooked the phrase: "exactly one neighbor". Sorry :-D

SUCCESSFUL SUBMISSIONS


Fetching successful submissions