Gyönyörű geometriai mintázatokat árulsz, amelyek 1x1-es négyzet alakú csempékből állnak. A csempék nem fedik át egymást.Például:


A kék csempéket '#' karakter, a fehéreket '.' karakter jelöli. Más színeket nem használsz.

Mivel nem mindenki szereti a kéket, néhány vevőd szeretné pirosra cserélni a minta kék részeit. Sajnos a piros csempék csak  2x2-es méretben kaphatók, és nem lehet feldarabolni őket.

Egy kék csempékből álló 2x2-es rész helyettesíthető egyetlen piros csempével, és ez addig ismételhető, amíg van ilyen 2x2-es rész. De arra vigyázni kell, hogy a piros csempék sem fedhetik egymást, és nem lóghatnak ki az eredeti képből. Például a fenti minta így alakítható át:


Minden piros csempe két '/' karakterből (bal-felső, jobb-alsó) és két  '\' karakterből áll össze.

Írjunk programot, ami eldönti, hogy a kék-fehér minta átalakítható-e a piros-fehér mintába.

A bemenet első sora a tesztesetek  T számát adja meg, utána pedig minden teszteset első sora a minta sorainak R és oszlopainak C számát. Ezután pedig a minta következik, a fent leírt kódolás szerint.

Minden tesztesethez írjuk ki a piros-fehér minta megfelelő kódolását, vagy az 'Impossible' szöveget, ha az átalakítás nem végezhető el.

Méretek

Kis bemenet

Nagy bemenet

Bemenet	Kimenet
3 2 3 ### ### 1 1 . 4 5 .##.. .#### .#### .##..	Case #1: Impossible Case #2: . Case #3: ./\.. .\//\ ./\\/ .\/..

A feladat forrása: Google Code Jam 2011 1C ( online tesztelő )

Algoritmusok: mohó algoritmus

megoldás