5. Prestavba bytu

Krtko rekonštruuje byt. Posledné, čo mu zostáva je vydláždiť novú kúpeľňu. Zhodou náhod sa mu v schránke objavil leták obľúbeného veľkoskladu - Kúpeľňového Sveta Podláh - a v ňom zľava na dlaždice L-kového tvaru. Táto ponuka bola natoľko lákavá, že Krtko nakúpil oveľa viac dlaždíc, ako potreboval. Teraz sedí pred svojou dokonalou dokonalo-štvorcovou kúpeľňou a premýšľa, či on vôbec bude vedieť pomocou týchto kachličiek svoju kúpeľňu vydláždiť. Akoby nestačilo, v jeho inak príjemne dokonalo-štvorcovej kúpeľni sa nachádza otvor na odtok sprchy, ktorý nemôže kachličkami prekryť. Pomôžte Krtkovi vydláždiť jeho kúpeľňu alebo zistite, že to nie je možné.

Úloha

Štvorcovú kúpeľňu si môžeme predstaviť ako štvorcovú sieť \(n \times n\). Pre dokonalo štvorcovú kúpeľňu navyše platí, že veľkosť jej strany \(n\) je mocnina dvojky. Odtok zaberá v myslenej sieti práve jedno celé políčko. Pod dlaždicou L-kového tvaru myslíme tri štvorce veľkosti \(1 \times 1\), spojené do tvaru L.

Vykachličkovanie je možné, ak pomocou L-kových kachličiek vieme prekryť všetky voľné miesta v našej kúpeľni (okrem odtoku) bez toho, aby sme nejaké kachličky akokoľvek delili alebo ľubovolne prekrývali. Taktiež sa nesmie stať, že by nejaká kachlička vyčnievala z kúpeľne. Samozrejme, nakúpené kachličky je možné akokoľvek otáčať. Kachlička teda môže byť orientovaná 4 rôznymi spôsobmi.

Na vstupe od nás dostanete veľkosť kúpeľne. Ďalej od nás dostanete pozíciu odtoku. Ak je možné kúpeľňu takýchto rozmerov s odtokom na danom mieste vykachličkovať iba pomocou nakúpených L-kových kachličiek, vypíšte ľubovolné takéto vykachličkovanie. Ak to možné nie je, podajte o tom správu.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n\) \((1 \leq n \leq 256)\) – dĺžka hrany štvorca reprezentujúceho kúpeľňu, pričom platí, že \(n\) je mocnina 2. V ďalšom riadku nasleduje dvojica čísel \(r, s\) \((1 \leq r, s \leq n)\) – číslo riadku a stĺpca v našej mriežke, kde sa nachádza odtok.

Formát výstupu

Ak vykachličkovanie nie je možné, vypíšte na jeden riadok výstupu reťazec Neda sa. Inak si označme všetky použité kachličky číslami od 1 do \(x\), kde \(x\) je ich počet (je zrejmé, že \(x = (n^2-1) \div 3\)). Na výstup vypíšte \(n\) riadkov. V každom takomto riadku sa má nachádzať \(n\) medzerou oddelených reťazcov. Ako \(j\)-ty reťazec v \(i\)-tom riadku vypíšte číslo kachličky, ktorá prekrýva poličko v \(i\)-tom riadku a \(j\)-tom stĺpci mriežky alebo vypíšte znak X ak sa na danom políčku nachádza odtok. Korektných riešení môže byť viac (napríklad prečíslovaním kachličiek dostaneme z jedného korektného riešenia iné korektné riešenie). Vypíšte ktorékoľvek z nich.

Hodnotenie

Vaše riešenia budú testované na štyroch sadách testovacích vstupov, pre ktoré platí:

Príklady

Input:

2
1 1

Output:

X 1
1 1

Kúpeľna veľkosti \(2 \times 2\) s odtokom v ľavom hornom rohu. Je len jedno možné riešenie.

Input:

4
2 3

Output:

2 2 1 1
2 3 X 1
4 3 3 5
4 4 5 5

Jedno z možných riešení. Akékoľvek iné riešenie s iným prečíslovaním či inou pozíciou kachličiek bude tiež akceptované.