시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB278523.810%

문제

Как известно, в 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 цифр – номер первого дня календаря. Если вариантов восстановления несколько, можно вывести любой из них. Гарантируется, что хотя бы один способ восстановления существует.

예제 입력 1

1 2
23

예제 출력 1

23

예제 입력 2

3 3
1**
*1*
**1

예제 출력 2

109

예제 입력 3

2 3
9**
00*

예제 출력 3

999

예제 입력 4

3 4
****
*0**
01**

예제 출력 4

0098