Сапер

Обмеження: 2 сек., 256 МіБ

Школяре, ти колись грав у «Сапера»?

У цій задачі ми розглядаємо простішу версію цієї гри.

Є поле з мінами, яке задається рядком з \(n\) символів. Кожен символ рядка — це або порожня клітинка (.), або клітинка з міною (*).

Тобі зараз не треба грати в «Сапера», а тільки для кожної порожньої клітинки поля потрібно визначити, скільки мін є в сусідніх клітинках.

Вхідні дані

У першому рядку записано ціле число \(n\) — розмір поля.

Далі задано рядок з \(n\) символів — опис поля з мінами. \(i\)-ий символ рядка — це . (крапка), якщо \(i\)-а клітинка порожня, або *, якщо \(i\)-а клітинка містить міну.

Вихідні дані

Виведи рядок з \(n\) символів. Якщо \(i\)-а клітинка поля містить міну, то \(i\)-ий символ твоєї відповіді повинен бути *. Якщо ж \(i\)-а клітинка поля порожня, то \(i\)-ий символ відповіді повинен бути кількістю клітинок з мінами, сусідніх з \(i\)-ою клітинкою.

Обмеження

\(1 \le n \le 10^5\).

Оцінювання складається з таких блоків:

• по 1 балу за приклади з умови,

• 6 балів: поле не містить мін,

• 10 балів: кожна клітинка поля містить міну,

• 80 балів: без додаткових обмежень.

Бали за блок ти отримаєш тільки якщо твоя програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 .*.*...	1*2*100

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
13 .***...**.*.*	1***101**2*2*

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 ....	0000

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 ****	****

Примітки

У першому прикладі відповідь — 1*2*100.

Перша клітинка не містить міни. У першої клітинки є тільки одна сусідня — друга, і друга клітинка містить міну. Тому першим символом відповіді є 1.

Друга клітинка містить міну, тому другим символом відповіді є *.

Третя клітинка не містить міни. У третьої клітинки є дві сусідні — друга й четверта, які містять міни. Тому третім символом відповіді є 2.

Четверта клітинка містить міну, тому четвертим символом відповіді є *.

П’ята клітинка не містить міни. У п’ятої клітинки є дві сусідні — четверта й шоста, і тільки четверта містить міну. Тому п’ятим символом відповіді є 1.

Ні шоста клітинка, ні жодна її сусідня не містять мін, тому шостий символ відповіді — це 0.

Ні сьома клітинка, ні її сусідня шоста не містять мін, тому сьомий символ відповіді — також 0.