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