Đường Đi Nhỏ Nhất Trên Lưới

Cho lưới ô vuông kích thước $n\times n$, mỗi ô chứa một chữ cái in hoa (A-Z). Bạn đi từ ô trái trên $(1,1)$ đến ô phải dưới $(n,n)$, mỗi bước chỉ được đi sang phải hoặc xuống dưới. Đường đi tạo thành một xâu gồm $2n-1$ ký tự. Tìm xâu nhỏ nhất theo thứ tự từ điển.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$.

• $n$ dòng tiếp theo, mỗi dòng chứa $n$ chữ cái in hoa.

Dữ liệu ra

In ra xâu nhỏ nhất theo thứ tự từ điển.

Ràng buộc

• $1\le n\le 3000$

Ví dụ