Göydələnlər
Semestrin sonunda Arxitektura Akademiyasının tələbəsi Petya öyrəndi ki, təcili olaraq tapşırığı aşağıdakı kimi olan kurs layihəsini təhvil verməlidir: vahid kvadratlara bölünmüş N*N ölçülü kvadrat meydançada 1-dən N-dək mərtəbə hündürlükdə binanı hər bir kvadratda elə yerləşdirmək lazımdır ki, hər sətir və hər sütunda bütün binanın mərtəbəlilik meydançalarının sxemləri müxtəlif olsun.
Tapşırığın öhdəsindən vaxtında gələ bilməyəcəyini anlayan Petya yuxarı kurs yoldaşlarından onlarda oxşar tapşırığın işə yaramayan qaralamasının olub-olmamasını soruşdu. Xoşbəxtlikdən yuxarı kurs tələbələrindən biri Petyaya öz nəticələrini söylədi, lakin onlar olduqca çox qəribə idi.
Meydançanın sətir və sütunları üçün əgər ona soldan və ya sağdan(sətir üçün) baxsan və yuxarıdan və ya aşağıdan(sütun üçün) baxsan neçə bina olduğu göründüyü yazılmışdı. Bina o zaman görünən sayılır ki, onun qarşısında yüksək mərtəbəli bina yoxdur. Bundan başqa, qaralama xeyli köhnə olduğundan onun üzərindəki bəzi yazılar pozulmuşdu.
Verilmiş qaralamaya görə bu təsvirə uyğun heç olmasa evlərin yerləşmə variantlarından birini bərpa etməkdə Petyaya kömək edin.
Giriş verilənləri
Birinci sətirdə aralarında boşluq işarəsi olmaqla iki natural ədəd: kvadrat meydançanın ölçüsü N, 2 <= N <= 4, həmçinin binanın ən yüksək mərtəbəliliyi və qaralamada saxlanan yazıların K sayı, 0 <= K <= N*4 verilir.
Sonrakı K sayda sətirdə qaralamadakı yazılar aşağıdakı formatda verilir: sətir və ya sütunun nömrəsi, arada boşluq işarəsi, istiqamət (W –soldan sağa sətir, E – sağdan sola sətir, N – yuxarıdan aşağıya sütun, S – aşağıdan yuxarıya sütun), boşluq işarəsi, bu istiqamətdə görünən evlərin sayı. Sütunlar soldan sağa, sətirlər isə yuxarıdan aşağıya nömrələnir. Nömrələmə 1-dən başlayır.
Çıxış verilənləri
Çıxış faylında N sətir çıxışa verilir. Hər sətirdə aralarında boşluq işarəsi olmaqla N ədəd – sütunların nömrələrinin artma ardıcıllığında sətir meydançasına uyğun olaraq yerləşmiş binanın mərtəbələrinin sayı verilir. Evlərin son düzülüşü qaralamadakı yazılışın şərtlərini ödəməlidir. Əgər evlərin düzülüş variantları bir neçə dənədirsə, onlardan ixtiyari birini verin. Həll mümkün olmayan halda çıxışa "No solution" sözünü verin.