trasee

Cerință

Doi copii, Tren şi Bus, se plimbă de mână printr-o matrice cu $N$ linii şi $M$ coloane. Iniţial ei se găsesc în colţul din stânga–sus al matricei. Lui Bus îi place să meargă spre dreapta, iar lui Tren în jos. Astfel traseul celor doi va fi format numai din deplasări în poziţia vecină spre dreapta sau în jos. Visul lor este să treacă prin toate poziţiile matricei şi să revină în poziţia iniţială.

Atunci când se găsesc pe ultima coloană şi se deplasează spre dreapta, ei vor ajunge pe prima coloană a aceleiaşi linii, iar dacă se deplasează în jos de pe ultima linie, vor ajunge pe prima linie a aceleiaşi coloane. La fiecare deplasare ei notează pe o foaie litera B dacă deplasarea este spre dreapta, şi litera T dacă deplasarea este în jos.

Cunoscând $N$, $M$ şi un număr natural $K$ să se determine al $K$-lea traseu în ordine lexicografică care pleacă din colţul din sânga-sus, trece exact o dată prin fiecare poziţie şi revine în poziţia iniţială a matricei.

Date de intrare

Fişierul de intrare trasee.in conţine pe prima linie numerele $N$, $M$ şi $K$ cu semnificaţia din enunţ.

Date de ieșire

Fişierul de ieşire trasee.out trebuie să conţină un şir de $N \cdot M$ caractere format din literele $B$ sau $T$ reprezentând codificarea traseului cerut.

Restricții și precizări

• $1 \leq N \cdot M \leq 1 \ 000 \ 000$
• $1 \leq K \leq 10^{18}$
• pentru teste în valoare de $5$ puncte se asigură că $N \cdot M \leq 25$
• pentru alte teste în valoare de $10$ puncte se asigură că $N, M \leq 15$
• pentru alte teste în valoare de $20$ puncte se asigură că $N = M$, număr prim
• pentru alte teste în valoare de $35$ puncte se asigură că $N = M$
• pentru toate testele există soluţie
• Tren şi Bus în orice moment se află în aceeaşi celulă

Exemplul 1

trasee.in

2 2 2

trasee.out

TBTB

Exemplul 2

trasee.in

1 6 1

trasee.out

BBBBBB