Trong một buổi stream đặc biệt, anh DoMixi tìm được một tấm bản đồ kho báu dạng lưới ~n \times n~, mỗi ô chứa một chữ cái in hoa từ A đến Z. Kho báu nằm ở góc dưới bên phải, còn anh đang đứng ở góc trên bên trái — tất nhiên rồi, vì anh DoMixi lúc nào cũng xuất phát từ đầu.

Để đến kho báu, anh chỉ được di chuyển sang phải hoặc đi xuống ở mỗi bước. Dọc đường đi, anh ghi lại các chữ cái trên từng ô anh đi qua (kể cả ô xuất phát và ô đích) tạo thành một xâu độ dài ~2n - 1~.

Chat hỏi: "Anh ơi xâu nào đẹp nhất?" — anh DoMixi, người luôn tối ưu mọi thứ trong cuộc sống, quyết định chọn đường đi sao cho xâu thu được là nhỏ nhất theo thứ tự từ điển.

Hãy tìm xâu đó cho anh!

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 — mô tả lưới bản đồ.

Kết quả

In ra xâu nhỏ nhất theo thứ tự từ điển có thể thu được.

Ví dụ

Đầu vào:

4
ABCD
BBCA
BBAA
BAAA

Đầu ra:

ABBBAAA

Giải thích: Đường đi tối ưu là ~(0,0) \to (1,0) \to (2,0) \to (2,1) \to (2,2) \to (2,3) \to (3,3)~, thu được xâu ~ABBBAAA~. Anh DoMixi đi xuống trước để tránh các chữ C, D ở hàng đầu — chat gật gù hài lòng.

Giới hạn

• ~1 \le n \le 3000~
• Mỗi ô chứa một chữ cái in hoa từ ~\text{A}~ đến ~\text{Z}~

Subtask