Сапер

Limits: 2 sec., 256 MiB

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

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

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

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

Input

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

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

Output

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

Constraints

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

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

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

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

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

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
7 .*.*...	1*2*100

Input (stdin) сopy	Output (stdout) сopy
13 .***...**.*.*	1***101**2*2*

Input (stdin) сopy	Output (stdout) сopy
4 ....	0000

Input (stdin) сopy	Output (stdout) сopy
4 ****	****

Notes

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

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

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

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

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

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

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

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