Vasylko and Serhiyko are playing a game on a grid. Serhiyko draws one of the symbols , , , or in some cells of the grid. 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 it is possible to correctly draw all the required lines. Your task is to help Vasylko by writing a program that determines if it is possible to make the required connections.
A correct representation of a molecule must satisfy the following conditions:
Each line connects symbols drawn 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 ( for , for , for , and for ).
Empty cells, denoted by , are not connected to any symbols.
At least one cell contains a symbol.
The first line contains two natural numbers and (1 \leq n, m \leq 50), representing the dimensions of the grid. Each of the next lines contains symbols that describe Serhiyko's configuration of chemical elements; empty cells are denoted by the symbol .
Output a single word: Valid if the lines can be drawn as required, or Invalid otherwise.
Example 1