Збори. День другий

Список учасників

Задача "Зоряне небо"
На зоряному небі світяться зірки, об’єднані у сузір’я. Сузір’я - це непуста група поруч розташованих зірок, що мають сусідами зірки або по горизонталі, або по вертикалі, або по діагоналі. Сузір’я не може бути частиною іншого.

На небі можуть бути однакові сузір’я, тобто такі, що мають однакову форму незалежно від їх орієнтації. Число можливих орієнтацій для сузір’я - вісім (поворот на 90, 180, 270 градусів та зеркальне відображення).

Нічне небо представлено картою неба - двовимірним масивом з нулів та одиниць. 1 - зірка, 0 - немає зірки.

Завдання:
На заданій карті неба позначити маленькими літерами англійського алфавіту усі сузір’я. Однакові сузір’я позначити однією літерою.

Вхідні дані:
Вхідний файл Starry.in містить у першому рядку два числа: W - ширину карти, H - висоту карти (0 <= W, H <= 100). Далі у файлі містяться H рядків, кожен з яких містить W символів. Пробілів між символами немає.
Число сузір’їв від 0 до 500, число різних сузір’їв - від 0 до 26 (a ... z), число зірок у кожному сузір’ї - від 1 до 160.

Вихідні дані:
Файл Starry.out містить ту саму карту зоряного неба, що і вхідний файл, тільки сузір’я в ній позначені літерами.

Приклад вхідного файлу:
4 3
0100
0001
1001

Приклад вихідного файлу:
0a00
000b
a00b