Social Distancing in Seating Arrangements

In this problem, you are given a seating arrangement in a classroom represented as a grid with ( R ) rows and ( C ) columns. Each cell in the grid is either occupied ('X') or empty ('.'). Your task is to determine whether the seating arrangement adheres to the social distancing guidelines. The arrangement is considered valid if no two occupied seats are adjacent in any of the eight possible directions: up, down, left, right, and the four diagonal directions.

The input starts with two integers representing the number of rows ( R ) and columns ( C ). Then, ( R ) lines follow, each containing a string of length ( C ) that represents a row of the seating arrangement. The output should be either the string "valid" if the arrangement follows the guidelines or "invalid" if it does not.

inputFormat

The first line contains two integers ( R ) and ( C ) separated by spaces. Each of the next ( R ) lines contains a string of length ( C ) representing one row of the seating arrangement.

outputFormat

Output a single line containing either "valid" if the seating arrangement adheres to the guidelines, or "invalid" otherwise.## sample

3 3
.X.
...
.X.

valid