Bölmə#5545
İki mədənçıxarma şirkəti birgə qızıl çıxarmaq üçün əlverişli bir yer tapıblar. İndi isə torpaq sahəsinin şirkətlər arasında bölünməsi üçün ciddi danışıqlar aparılır.
Ərazi kvadrat formasındadır və n * n ölçülü vahid kvadratlara bölünmüşdür. Hər bir kiçik kvadrat ya boşdur, ya da bir və ya iki qızıl yatağı ehtiva edir. Siz bu ərazini iki əlaqəli sahəyə bölməlisiniz, lakin bu sahələrin eyni ölçüdə olması şərt deyil.
Şirkətlər üçün aşağıdakı sadə təkliflər nəzərə alınmalıdır. Onların sahələri arasındakı sərhəd şimal-qərb küncündən başlayıb cənub-şərqdə bitməlidir və vahid kvadratların sərhədləri boyunca uzanmalıdır. Sərhədin uzunluğu 2n-dən çox olmamalıdır. Hər iki sahə eyni sayda qızıl yatağına malik olmalıdır.
Birinci sətir testlərin sayını t göstərir. Sonra testlər gəlir.
Hər testin birinci sətiri sahənin tərəfinin uzunluğunu n (1 ≤ n ≤ 1000) göstərir. Növbəti n sətir sahənin təsvirini verir: hər bir sətir n ədəd ehtiva edir. Bu ədədlər vahid kvadratlarda qızıl yataqlarının sayını göstərir və 0, 1 və ya 2 ola bilər. Birinci sətir ən şimaldadır və hər bir sətir qərbdən şərqə doğru sıralanır.
Hər test üçün aşağıdakıları çıxarın:
IMPOSSIBLE sözü, əgər uyğun torpaq bölməsi mümkün deyilsə,
sərhədin təsviri, əgər uyğun torpaq bölməsi mümkündürsə. Şimal-qərb küncündən cənub-şərqə qədər sərhədi təsvir edən ən çox 2n hərfdən ibarət ardıcıllığı çıxarın. Hərflər sərhədin şimala, şərqə, cənuba və qərbə getdiyini göstərir.
Əgər bir neçə həll mövcuddursa, onlardan hər hansı birini çıxarın.
Nümunə 1