21580번 - Древний календарь 스페셜 저지다국어

문제

Как известно, в 2012 году человечество с повышенным вниманием относится к древним календарям. Особый интерес представляют те из них, которые не заканчиваются 2012 годом. Потрясающее открытие в этом направлении сделано археологами Татарстана. В древних захоронениях oни обнаружили прямоугольную табличку, которая после расшифровки сохранившихся знаков была записана в виде таблицы, состоящей из N строк по M десятичных цифр в каждой. Но полностью расшифровать табличку не удалось, так как некоторые цифры стерлись. Утраченные цифры в таблице были заменены символами «*».

По мнению археологов, найденная табличка представляет собой древний календарь, а записанные в ней M значные числа являются номерами последовательных дней некоторого периода. Первое число является номером первого дня этого периода, а каждое следующее число на единицу больше предыдущего. По этому календарю конец света отсутствует, и после дня, обозначаемого с помощью M девяток, следует номер дня из M нулей.

Требуется написать программу, которая восстанавливает утраченные цифры так, чтобы число в каждой строке таблицы, начиная со второй, было на единицу больше предыдущего, и выводит номер первого дня в найденном календаре.

입력

В первой строке входного файла записаны натуральные числа N и M – количество строк в таблице и длина каждой строки соответственно (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000, M×N ≤ 100 000). Далее следуют N строк по M символов в каждой, состоящих только из десятичных цифр от 0 до 9 и символов «*».

출력

Выходной файл должен содержать одну строку, состоящую из M цифр – номер первого дня календаря. Если вариантов восстановления несколько, можно вывести любой из них. Гарантируется, что хотя бы один способ восстановления существует.

제한

힌트