Вася и Серёжа играют в следующую игру. В некоторых клетках клетчатого листка Серёжа рисует один из символов "\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}, если нельзя.