Bạn được cho một lưới \(n \times n\), trong đó mỗi ô chứa một chữ cái.

Bạn cần đi từ ô góc trên bên trái đến ô góc dưới bên phải. Bạn chỉ được đi sang phải hoặc đi xuống.

Chuỗi nhỏ nhất theo thứ tự từ điển mà bạn có thể tạo ra là gì?

Input

Dòng đầu tiên chứa một số nguyên \(n\): kích thước của lưới.

Sau đó có \(n\) dòng mô tả lưới. Mỗi dòng chứa \(n\) chữ cái từ A đến Z.

Output

In chuỗi nhỏ nhất theo thứ tự từ điển.

Constraints

• \(1 \le n \le 3000\)

Example

4
AACA
BABC
ABDA
AACA

AAABACA