Tələbələrə - pulsuz!
Böyük qalaktik teatr zalı S sıradan ibarətdir və hər sırada S yer mövcuddur. Hər tamaşa üçün bilet satışı aşağıdakı qaydada həyata keçirilir: ilk S^2-N nəfər bilet alarkən istədikləri yerləri seçə bilərlər, qalan N kreslo isə ənənəyə uyğun olaraq tələbələrə pulsuz verilir.
Cinsi ayrı-seçkilik ittihamlarından qaçmaq üçün tələbələri bu N yerə elə yerləşdirmək lazımdır ki:
hər sırada qız və oğlan tələbələrin sayı 1-dən çox fərqlənməsin;
hər "yerlərin vertikalında" (yəni eyni nömrəli, lakin müxtəlif sıralarda yerləşən yerlərdə) qız və oğlan tələbələrin sayı da 1-dən çox fərqlənməsin.
Beləliklə, gözəllik sevərlərə bilet satıldıqdan sonra təşkilatçılar qalan N kreslonu qadın və kişi olaraq bu qaydalara uyğun bölüşdürməlidirlər.
Zaldakı hər yer 1-dən S-ə qədər iki rəqəmlə müəyyən edilir - sıranın nömrəsi və həmin sıradakı yerin nömrəsi. Tələbə kreslosu nömrə i a_i-ci sırada yerləşir və həmin sırada b_i nömrəsinə malikdir. Gözəllik sevərləri istənilən yerləri tuta bildikləri üçün, a_i və b_i rəqəmləri 1-dən S-ə qədər istənilən dəyəri ala bilər. Xüsusilə, elə ola bilər ki, hansısa sırada heç bir tələbə yeri olmasın.
Təşkilatçılar işlərini asanlaşdırmaq üçün sizdən tələbə yerlərinin kişi və qadın olaraq bölüşdürülməsini avtomatlaşdıran bir proqram yazmağı xahiş edirlər.
Giriş verilənləri
Əvvəlcə iki tam ədəd S və N (1 ≤ S ≤ 100000, 1 ≤ N ≤ min{100000, S^2}) daxil edilir. Sonra N cüt təbii ədəd (a_i, b_i) verilir ki, bunlar S-i keçmir. Bütün yerlərin fərqli olduğu təmin edilir.
Çıxış verilənləri
Əgər axtarılan üsul mövcud deyilsə, Impossible çıxarın. Əks halda, N simvoldan ibarət tək bir sətir çıxarın, burada 'M' (kişi) və 'W' (qadın) simvolları var. i-ci mövqedəki simvol, giriş məlumatlarında sadalanan eyni nömrələmə ilə i-ci yerin statusuna uyğundur.