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 intrate rebus1.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 rebus1.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 x 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 <= n, m <= 100
• Se vor folosi numai litere mari. Lungimea maximă a unui cuvânt este 40.
• Pentru toate datele de test există soluţie.

Exemple

rebus1.in	rebus1.out	Explicaţii
13 ION ARELANUL XIS PUSIE CANIT	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

autor: Prof. Marinel Şerban

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com