Se consideră o matrice pătratică cu 16 linii și 16 coloane. Elementele acestei matrice pot fi 0 sau 1. Această matrice reprezintă, de fapt, o literă a alfabetului englezesc (litera este formată din elementele a căror valoare este 1). Va trebui să determinați care este litera reprezentată de această matrice.
    În acest scop veți avea la dispoziție un număr de N matrice pătratice cu 16 linii și 16 coloane care conțin reprezentări standard ale literelor. Litera corespunzătoare matricei date este dată de "cea mai apropiată matrice dintre cele N".
    Va trebui să definim distanța dintre două matrice. Pentru a determina o astfel de distanță, fiecărui element cu valoarea 1 din prima matrice va trebui să îi corespundă un element cu valoarea 1 din cea de-a doua matrice și fiecărui element cu valoarea 1 din cea de-a doua matrice să îi corespunda un punct din prima matrice.
    Așadar se va realiza o corespondență între elementele celor două matrice. Presupunem, fără a restrânge generalitatea, că prima matrice conține mai multe elemente cu valoarea 1 decât a doua. Numărul elementelor cu valoarea 1 din prima matrice va fi notat cu p, iar numărul elementelor cu valoarea 1 din cea de-a doua va fi notat cu q. În aceste condiții, fiecărui element cu valoarea 1 din cea de-a doua matrice îi vor corespunde [p/q] elemente din prima matrice. Dacă q nu este divizor al lui p, vor rămâne elemente în prima matrice care nu au corespondent. Acestora le vor corespunde elemente distincte din cea de-a doua matrice. Cu alte cuvinte, corespondențele vor fi "echilibrate", în sensul că dacă unui element dintr-o matrice îi corespund k elemente (și acest k este minimul numărului de elemente corespunzătoare elementelor din matrice), atunci tuturor celorlalte elemente le vor corespunde fie k, fie k + 1 elemente.
     Distanța dintre două matrice va fi dată de suma distanțelor dintre elementele puse în corespondență. Dacă un element de pe poziția (i1, j1) în prima matrice îi corespunde un element (i2, j2) în cea de-a doua, atunci distanța dintre cele două elemente va fi |i1 - i2| + |j1 - j2|.
     Evident, corespondențele trebuie alese în așa fel încât distanța dintre cele două matrice să fie cât mai mică posibil.

Fișierul de intrare OCR.IN conține pe primele 16 linii elementele matricei care reprezintă litera care trebuie recunoscută.
    Pe următoarea linie se va afla numărul N al literelor date. Va urma descrierea literelor. Pentru fiecare literă vom avea 17 linii.
    Prima dintre ele va identifica litera (un caracter). Următoarele 16 linii vor conține descrierea literei.
    Valorile de pe o linie nu vor fi separate prin spații.

Fișierul de ieșire OCR.OUT trebuie să conțină o singură linie pe care se va afla un singur caracter reprezentând litera recunoscută.

  • 1 <= N <= 26;
  • fiecare matrice va conține cel puțin unul și cel mult 100 de elemente cu valoarea 1;
  • literele descrise nu vor fi neapărat distincte;
  • va exista întotdeauna o singură soluție.


  • OCR.IN
    0000000000000000
    0000000000000000
    0000000000000000
    0000000100000000
    0000001010000000
    0000010001000000
    0000100000100000
    0001000000010000
    0001000000010000
    0001111111110000
    0001000000010000
    0001000000010000
    0001000000010000
    0000000000000000
    0000000000000000
    0000000000000000
    2
    A
    0000000000000000
    0000000000000000
    0000000100000000
    0000001110000000
    0000010001000000
    0000100000100000
    0001000000010000
    0001100000110000
    0001111111110000
    0001100000110000
    0001000000010000
    0001000000010000
    0001000000010000
    0000000000000000
    0000000000000000
    0000000000000000
    C
    0000000000000000
    0000000000000000
    0000000000000000
    0000111111111100
    0001111000000010
    0001110000000100
    0001100000000000
    0001100000000000
    0001100000000000
    0001100000000000
    0001100000000000
    0001100000000000
    0001110000000100
    0001111000000010
    0000111111111100
    0000000000000000

    OCR.OUT
    A