Хімія!!!
Василько та Сергійко грають у наступну гру. У деяких клітинках клітчатого аркуша Сергійко малює один з символів "H", "O", "N" або "C", після чого Вася повинен провести мвж деякими символами, які знаходяться у сусідніх клітинках, лінії так, щоб отримати коректне зображення хімічної молекули. На жаль, Сергійко полюбляє малювати багато символів, і Василько не може відразу визначити, чи можливо взагалі намалювати лінії потрібним способом. Допоможіть йому написать програму, яка дасть відповідь на це питання.
У цій задачі проведені між символами хімічних елементів лінії будемо вважати коректним зображенням молекули, якшо вони задовольняють наступним умовам:
кожна лінія з'єднує символи, намальовані у сусідніх (по стороні) клітинках,
між кожною парою символів проведено не більше однієї лінії,
від кожного елемента відходить рівно стільки ліній, яка валентність цього елементу (1 для H, 2 для O, 3 для N і 4 для C,
порожні клітинки ні с чим не з'єднані, і
хоча б у одній клітинці намальовано якийсь символ.
Вхідні дані
Перший рядок вхідного файлу містить два натуральних числа n та m (1 ≤ n, m ≤ 50) - розміри аркуша, на якому малює Сергійко. Далі йде n рядків по m символів у кожному, які задають конфігурацію хімічних елементів, яку намалював Сергійко; порожін клітинки задаються символом ".".
Вихідні дані
У вихідний файл виведіть одне слово: Valid, якщо лінії провести потрібни чином можні, і Invalid, якщо ні.