rebus

Fie dat un şir de caractere format NUMAI din litere mari ale alfabetului englez şi caracterul spaţiu. Acesta reprezintă conţinutul unui careu de rebus citit pe linii de sus în jos, iar fiecare linie de la stânga spre dreapta.

Cerinţă

Să se determine dimensiunile careului precum şi cuvintele din careu care au minim $2$ caractere, indicând pentru fiecare cuvânt căsuţa de unde începe şi dacă este orizontal sau vertical. Se mai cunoaşte de asemenea numărul de cuvinte formate din minim două litere din careu.

Date de intrare

Fişierul de intrare rebus.in conţine pe prima linie numărul de cuvinte de minim $2$ caractere care există în careu. Linia a doua a fişierului de intrare conţine şirul de caractere care reprezintă conţinutul careului.

Date de ieşire

Fişierul de ieşire rebus.out conţine pe prima linie două numere naturale $n \; m$ care reprezintă numărul de linii respectiv numărul de coloane ale rebusului. Fiecare dintre liniile următoare conţine câte un cuvânt. Cuvintele vor fi afişate în ordine alfabetică sub forma: $cuvant \ L \ C \ tip$

unde $cuvant$ este cuvântul, $L$ - linia de unde începe, $C$ - coloana, $tip$ ('O' sau 'V'). În cazul în care două cuvinte sunt egale se va afişa mai întâi cuvântul cu numărul de linie mai mic. Dacă şi numărul de linie coincide se va afişa mai întâi cuvântul care are numărul coloanei mai mic. În cazul în care şi coloana coincide, se va afişa mai întâi cuvântul de pe orizontală (tip 'O').

Restricţii

• Dimensiunile careului sunt maxim $100 \times 100$, deci şirul iniţial de caractere poate avea maxim $10000$ caractere.
• Liniile careului se numerotează de la $1$ de sus în jos, iar coloanele se numerotează de la $1$ de la stânga spre dreapta.
• Şirul de caractere nu începe şi nu se termină cu spaţiu.
• $2 \leq n, m \leq 100$
• Se vor folosi numai litere mari. Lungimea maximă a unui cuvânt este $40$.
• Pentru indicarea corectă a numărului de linii şi de coloane ale careului se va acorda $20\%$ din punctaj. Pentru identificarea corectă a cuvintelor careului se va acorda încă $40\%$ din punctaj, iar dacă acestea vor fi afişate corect ordonate se va acorda încă $40\%$ din punctaj.
• În toate cazurile există soluţie.

Exemplu

rebus.in

13
ION ARELANUL XIS PUSIE CANIT

rebus.out

4 7
ALUN 1 5 V
ARE 1 5 O
CANIT 4 3 O
EXIT 1 7 V
ILIE 1 1 V
ION 1 1 O
IS 3 1 O
LANUL 2 1 O
NN 1 3 V
OAS 1 2 V
PUSI 3 4 O
SI 3 6 V
UPA 2 4 V

Explicație