Chemistry!!!
Vasylko and Serhiyko are playing a game on a grid. Serhiyko draws one of the symbols "H", "O", "N", or "C" on some of the grid's cells. Vasylko's task is to connect these symbols with lines between adjacent cells to form a valid chemical molecule. However, Serhiyko often draws many symbols, making it difficult for Vasylko to immediately determine if the connections can be made correctly. Your task is to help Vasylko by writing a program that determines if it's possible to draw the lines as required.
A correct representation of a molecule must meet the following conditions:
Each line connects symbols in adjacent cells (sharing a side).
No more than one line is drawn between any pair of symbols.
The number of lines emanating from each symbol must match the valency of the element: 1 for H, 2 for O, 3 for N, and 4 for C.
Empty cells, denoted by ".", are not connected to any symbols.
At least one cell must contain a symbol.
Input
The first line of input contains two natural numbers n and m (1 ≤ n, m ≤ 50), representing the dimensions of the grid. The next n lines each contain m characters, depicting the configuration of chemical elements drawn by Serhiyko. Empty cells are represented by the symbol ".".
Output
Output a single word: Valid if the lines can be drawn to satisfy the conditions, or Invalid if they cannot.