Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

New Zealand Programming Contest 2023

NZPC2023

MOLECULES

Organic molecules can be amazingly complex and need a great variety   of    shapes    and   conventions   to    represent    them, particularly  if we wish to depict details of their 3-dimensional structures.   For  this   problem,  we  will   restrict  ourselves  to reasonably simple compounds with only single bonds between atoms, that can  be  represented  on  a  simple  rectangular  grid with bonds aligned horizontally or vertically. In such molecules, carbon is bonded to 4 adjacent atoms, nitrogen to 3, oxygen to 2 and hydrogen to 1. These numbers are called the valences of the atoms.

Of  course,  not  all  such  grids  represent  valid  molecules.  Your  task  is  to  write  a program that will determine whether a given grid could represent one or more valid molecules, satisfying the valences of all the atoms. Note that the molecule(s) in a valid grid do not need to exist in the real world.

Input

The first line of the input consists of a pair of integers (r and c, 1 ≤ r, c ≤ 20) representing the number of rows and columns in the rectangle to follow. The next r lines contain c characters each, where the characters are chosen from the set {‘H’, ‘O’, ‘N’, ‘C’, ‘.’} representing hydrogen, oxygen, nitrogen, carbon and ‘empty’, respectively.

Output

Output consists of a single line containing a single word:

·  Valid   if   it   possible   to   draw    horizontal   and/or   vertical   bonds   between neighbouring atoms so as to satisfy the valences of all the atoms in the grid, or

  Invalid if no such set of bonds exists.

Sample Input #4

4 10

OOOONOOOOO

OOOOHOOOOO

OOOHNHHOOO

OOOOOOOOOO

Output for Sample Input #4

Invalid