minime

Pentru a putea ţine evidenţa mai uşor, administratorul unui magazin întocmeşte o listă cu produsele care se găsesc în magazin la începutul zilei. El scrie numele produselor, folosind cuvinte de aceeaşi lungime, formate doar din literele mici ale alfabetului englez. Îndată finalizată lista, el îi asociază un cod reprezentând cel mai mic cuvânt în sens lexicografic, obţinut prin preluarea unei litere din fiecare nume de produs, în ordinea în care acestea au fost scrise pe listă.

El observă că acest cod poate fi obţinut în mai multe moduri. Doreşte însă să identifice varianta în care literele alese sunt cât mai apropiate, altfel spus, distanţa, reprezentând numărul de poziţii, între poziţia cea mai mică şi poziţia cea mai mare pe care sunt plasate caracterele alese, este minimă. De exemplu:

Pentru lista care cuprinde produsele de mai jos	Codul asociat este	O variantă de obţinere în care distanţa este 4. Poziţia literei a din al doilea cuvânt este 2 iar a lui e, ales în al treilea cuvânt este 5.	Varianta optimă este caracterizată de distanţa 2. deoarece, poziţia minimă a unui caracter ales este 2 iar cea maximă este 3.
	aaea

Cerinţă

Fişierul minime.in conţine pe prima linie o pereche de numere naturale $N$ şi $M$ reprezentând numărul de produse scrise pe listă şi numărul de litere ale fiecărui nume de produs. Pe următoarele $N$ linii se găsesc şiruri de câte $M$ caractere litere mici reprezentând numele produselor, în ordinea în care au fost scrise în listă.

Date de intrare

Fişierul minime.in conţine pe prima linie o pereche de numere naturale $N$ şi $M$ reprezentând numărul de produse scrise pe listă şi numărul de litere ale fiecărui nume de produs. Pe următoarele $N$ linii se găsesc şiruri de câte $M$ caractere litere mici reprezentând numele produselor, în ordinea în care au fost scrise în listă.

Date de ieșire

Fişierul de ieşire minime.in va conţine $2$ linii:
a) pe prima linie, se va afişa un şir de caractere format din $N$ litere mici reprezentând codul asociat listei;
b) pe a doua linie, se va scrie un număr natural reprezentând distanţa minimă în care poate fi obţinut;

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $1 \leq M \leq 255$
• Cuvântul $A_1A_2…A_N$ este mai mic lexicografic decât $B_1B_2…B_N$, dacă există un indice $K \leq N$ astfel încât $A_i= B_i$ pentru orice $i < K$ şi $A_K < B_K$;
• Pentru $50\%$ din teste $N \leq 8 \ 000$;
• Pentru rezolvarea corectă doar a cerinţei a) se acordă $20\%$ din punctaj iar pentru rezolvare corectă a ambelor cerinţe se acordă $100\%$ din punctajul pe test.

Exemplu

minime.in

5 5
inele
cacao
ardei
lapte
peste

minime.out

eaaae
3 

Explicație

Distanţa minimă este 3 şi se obţine astfel:
inele
cacao
ardei
lapte
peste