Василько та Сергійко грають у наступну гру. У деяких клітинках клітчатого аркуша Сергійко малює один з символів "H", "O", "N" або "C", після чого Вася повинен провести мвж деякими символами, які знаходяться у сусідніх клітинках, лінії так, щоб отримати коректне зображення хімічної молекули. На жаль, Сергійко полюбляє малювати багато символів, і Василько не може відразу визначити, чи можливо взагалі намалювати лінії потрібним способом. Допоможіть йому написать програму, яка дасть відповідь на це питання.

У цій задачі проведені між символами хімічних елементів лінії будемо вважати коректним зображенням молекули, якшо вони задовольняють наступним умовам:

кожна лінія з'єднує символи, намальовані у сусідніх (по стороні) клітинках,

між кожною парою символів проведено не більше однієї лінії,

від кожного елемента відходить рівно стільки ліній, яка валентність цього елементу (1 для H, 2 для O, 3 для N і 4 для C,

порожні клітинки ні с чим не з'єднані, і

хоча б у одній клітинці намальовано якийсь символ.

Формат вхідних даних

Перший рядок вхідного файлу містить два натуральних числа \(N\) та \(M\) (\(1 \le N, M \le 50\)) - розміри аркуша, на якому малює Сергійко. Далі йде \(N\) рядків по \(M\) символів у кожному, які задають конфігурацію хімічних елементів, яку намалював Сергійко; порожін клітинки задаються символом ".".

Формат вихідних даних

У вихідний файл виведіть одне слово: Valid, якщо лінії провести потрібни чином можні, і Invalid, якщо ні.

Приклад вхідних даних-1

3 4
HOH.
NCOH
OO..

Приклад вихідних даних-1

Valid