Chemistry!!!#1752

Chemistry!!!

1 second
64 megabytes
Easy

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:

Input

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

Output a single word: Valid if the lines can be drawn as required, or Invalid otherwise.

Examples

Example 1

Loading
Loading