eolymp
bolt
Try our new interface for solving problems
Problems

Максимальное число

Максимальное число

Time limit 2 seconds
Memory limit 256 MiB

Дана таблица цифр размером N×N. Пометим в ней N элементов таким образом, чтобы из каждой строки и каждого столбца был помечен ровно один элемент.

Далее составим из всех помеченных цифр число так, что его первой цифрой взята цифра, помеченная в первой строке, второй – во второй, и так далее.

Например, из помеченных в следующей таблице цифр мы таким образом получим число 4307:

Определите, какое максимальное число можно получить вышеописанным способом из данной таблицы.

Input data

Первая строка содержит целое число N (2N100). Далее следует сама таблица - каждая из следующих строк содержит N цифр без пробелов или каких-либо других разделителей. Цифры в таблице от 0 до 9 включительно.

Output data

Выведите максимальное число, которое можно получить из данной таблицы. Не пропускайте ведущих нулей (см. пример № 2).

Examples

Input example #1
4
2421
3420
1300
8187
Output example #1
4308
Author Николоз Джимшелеишвили
Source Зимняя школа, Харьков 2009, контест Теодора Заркуа и его учеников