Cậu bé Greedy được tặng một tấm bảng nhân dịp sinh nhật của cậu. Tấm bảng có ~N~ hàng và ~M~ cột, mỗi ô giao giữa hàng và cột chứa một chữ cái in thường trong bảng chữ cái tiếng Anh. Vào bữa tiệc sinh nhật, mọi người cảm thấy buồn chán và đã quyết định chơi một trò chơi trên bảng.
Trò chơi bắt đầu bằng việc đặt một đồng xu ở ô trên cùng bên trái của bảng là ô ~(1,1)~. Ở mỗi lượt chơi, người chơi phải di chuyển đồng xu xuống một ô bên dưới hoặc sang một ô bên phải, điều kiện là đồng xu đó phải vẫn còn nằm trên bảng. Trò chơi kết thúc khi đưa được đồng xu tới ô dưới cùng bên phải là ô ~(N,M)~. Trong suốt quá trình chơi, người chơi ghi lại mảng những kí tự thu được khi di chuyển đồng xu, và tạo thành được một từ. Mục tiêu của trò chơi là tạo ra được từ có thứ tự từ điển nhỏ nhất.
Những người chơi thắng cuộc sẽ nhận được phần thưởng là một túi kẹo khổng lồ. Greedy muốn thắng được túi kẹo đó bằng mọi giá, vì vậy cậu ấy nhờ bạn viết một chương trình tìm ra từ có thứ tự từ điển nhỏ nhất có thể tạo được.
Ghi chú: Thứ tự từ điển của các từ là thứ tự mà các từ đó xuất hiện trong từ điển. Nếu chúng ta có hai từ, và chúng khác nhau ở chữ cái đầu tiên, thì từ nhỏ hơn sẽ là từ có chữ cái đầu tiên xuất hiện trước trong bảng chữ cái tiếng Anh.
Input
- Dòng đàu tiên gồm hai số nguyên ~N~ và ~M~ ~(1 \leq N, M \leq 2000)~.
- ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ chữ cái viết thường biểu diễn tấm bảng.
Output
In ra từ có thứ tự từ điển nhỏ nhất có thể tạo được
Sample 1
Input
4 5
ponoc
ohoho
hlepo
mirko
Output
pohlepko
Giải thích
Một trong những cách tạo được từ có thứ tự từ điển nhỏ nhất:
Sample 2
Input
4 5
bbbbb
bbbbb
bbabb
bbbbb
Output
bbbbabbb
Sample 3
Input
2 5
qwert
yuiop
Output
qweiop
Subtask
- ~8~ test có dữ liệu đầu vào đảm bảo rằng: tại mỗi ô, ô bên phải và ô bên dưới nó có chữ cái khác nhau
- ~8~ test còn lại không có ràng buộc gì thêm
Bình luận