Древний календарь
면접 대비시간 제한1초메모리 제한1024 MB
N행 M자리 숫자 표에서 지워진 자리를 복원해 각 행이 이전 행보다 1 큰 수가 되도록 하고, 첫째 행의 수를 출력한다.
문제
Как известно, в 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 цифр – номер первого дня календаря. Если вариантов восстановления несколько, можно вывести любой из них. Гарантируется, что хотя бы один способ восстановления существует.