Fişierul intrare/ieşire:	drum6.in, drum6.out	Sursă	Algoritmiada 2015, Runda 2
Autor	Mihai Calancea	Adăugată de	Heidelbacher Andrei •a_h1926
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Drum6

Cu toţii ştim cât de mult îi place lui Trăncănici să vorbească. Atât de mult, încât cu o seară înainte a avut un vis foarte ciudat...

Acesta se afla în căsuţa (1, 1) dintr-o matrice cu N linii şi M coloane. Fiecare căsuţă din matrice conţine o literă mică a alfabetului englez. În vis, el avea o misiune destul de grea. Pornind din căsuţa (1, 1), acesta trebuia să ajungă în căsuţa (N, M) din matrice, mergând la fiecare pas doar în dreapta sau în jos. Pentru că există foarte multe astfel de drumuri iar Moş Ene îşi dă seama că Trăncănici va vorbi foarte mult gândindu-se la toate posibilităţile, visul îi cere să aleagă drumul minim lexicografic.

Date de intrare

Fişierul de intrare drum6.in conţine pe prima linie două numere naturale N şi M, reprezentând dimensiunile matricei. Fiecare din următoarele N linii conţin câte M caractere (litere mici ale alfabetului englez), reprezentând conţinutul matricei.

Date de ieşire

În fişierul de ieşire drum6.out se va găsi un şir format din N + M - 1 caractere, reprezentând drumul minim lexicografic din căsuţa (1, 1) în căsuţa (N, M) a matricei.

Restricţii

• 1 ≤ N, M ≤ 1000

Exemplu

Cum se trimit solutii?