PROBLEMA 15:            Blatistul
DEADLINE:               Luni, 5 aprilie 1999
DOMENIU:                Backtracking
TIMP DE IMPLEMETARE:    O ora
PUNCTAJ:                50 dexteri

In orasul B. biletele de autobuz au o grila de NxN patratele, dintre
care aparatele de taxat composteaza (gauresc) K patratele. Biletul
poate fi introdus in aparat numai cu un capat (celalalt capat fiind
prins in cotor), dar poate fi introdus fie pe fata, fie pe dos. In
acest fel, unele din configuratiile posibile de K gauri in grila de
NxN sunt oglindiri stanga-dreapta ale altor configuratii. Iata un
exemplu pentru N=3 si K=2:

     +---+---+---+                            +---+---+---+
     | * |   |   |                            |   |   | * |
     +---+---+---+                            +---+---+---+
     |   |   | * |     este oglindirea lui    | * |   |   |
     +---+---+---+                            +---+---+---+
     |   |   |   |                            |   |   |   |
     +---+---+---+                            +---+---+---+

      (cod: 1123)                              (cod: 1321)

Un blatist inveterat face colectie de bilete perforate si doreste sa
catalogheze toate configuratiile posibile de gauri, ignorand insa
oglindirile (deoarece controlorii nu se supara daca un bilet este
taxat pe dos). In acest scop, el codifica fiecare configuratie
printr-un sir de forma:

l1c1l2c2...lkck

unde (li, ci) sunt coordonatele gaurii i relativ la coltul din
stanga-sus al biletului. Gaurile sunt enumerate de la stanga la
dreapta si de sus in jos. De exemplu, cele doua configuratii de mai
sus sunt codificate prin "1123" si "1321". Acum blatistul este capabil
sa elimine oglindirile dupa urmatorul criteriu: daca o configuratie
este oglindirea alteia, dintre cele doua se va clasifica numai cea a
carei codificare are o pozitie alfabetica minima, cealalta
ignorandu-se. Dintre cele doua configuratii de mai sus, "1123" are o
pozitie alfabetica minima (adica s-ar afla inaintea lui "1321" in
cartea de telefon).

DATE DE INTRARE: Fisierul BILET.IN contine valorile lui N si K
separate printr-un spatiu. Limite: 2<=N<=8, 1<=K<=3.

DATE DE IESIRE: Fisierul BILET.OUT va contine pe fiecare linie
codificarea unei configuratii, fara oglindiri. Configuratiile trebuie
scrise IN ORDINE ALFABETICA (pentru ca blatistul sa poata regasi cu
usurinta orice bilet).

EXEMPLU:

BILET.IN                        BILET.OUT (126 octeti)
3 2                             1112
                                1113
                                1121
                                1122
                                1123
                                1131
                                1132
                                1133
                                1221
                                1222
                                1231
                                1232
                                2122
                                2123
                                2131
                                2132
                                2133
                                2231
                                2232
                                3132
                                3133

TIMP DE RULARE: O secunda per test (adica, backtracking, backtracking,
                da' nici chiar asa :) )