Задача D. Молекулы ≡

Условие

Органические вещества отличаются потрясающим разнообразием. Они различаются по химическому составу (по пропорциям составляющих вещество элементов), по химической формуле молекул (по порядку расположения и химическим связям атомов) и по пространственной форме молекул. Проблема восстановления по химическому составу органического вещества его химической формулы и проблема пространственного конфигурирования молекул по их химическим формулам - чрезвычайно актуальные задачи биоинформатики. К сожалению, они отличаются высокой вычислительной сложностью.

Рассмотрим проблему химической формулы и пространственной конфигурации органических молекул при следующих упрощающих предположениях:

1. вещество состоит только из атомов водорода H (валентность 1), кислорода O (валентность 2), азота N (валентность 3) и углерода C (валентность 4);
2. молекула или группа молекул вещества представляет собой плоскую прямоугольную решётку из m строк и n столбцов, в узлах которой могут находиться или атомы перечисленных элементов, или "дырки" - пустоты, не занятые никаким атомом;
3. каждый атом в решётке может быть связан с атомами, своими соседями по решётке, но с каждым соседом он связан не более чем одной связью, а общее число его связей совпадает с его валентностью.

Формат входного файла

Входной файл для программы описывает одну решетку. В его первую строку записаны через пробел два целых чисел M и N, задающих число строк и число столбцов этой решётки. Следующие M строк содержат ровно по N символов `H`, `O`, `N`, `C`, `.`, представляющих элементы или "дырки" в порядке слева направо в соответствующей строке решётки.

Формат выходного файла

Ограничения

Примеры тестов

3 4
HOH.
NCOH
OO..

Valid