Se le proporciona una cuadrícula de ~n \times n~, cada casilla contiene una letra. Debe desplazarse de la casilla superior izquierda a la casilla inferior derecha. Solo puede desplazarse hacia la derecha o hacia abajo.

¿Cuál es la cadena lexicográficamente mínima que puedes construir?

Entrada

• La primera línea tiene un entero ~n~: el tamaño de la cuadrícula.
• Después de esto, hay ~n~ líneas que describen la cuadrícula. Cada línea tiene ~n~ letras entre la A y la Z.

Salida

Imprima la cadena lexicográficamente mínima.

Restricciones

• ~1 \leq n \leq 3000~

Ejemplo de Entrada

4
AACA
BABC
ABDA
AACA

Ejemplo de Salida

AAABACA