Ripple Effect

Determine whether the given filled grid satisfies the rules of a Ripple Effect puzzle.

A Ripple Effect puzzle is played on a rectangular grid divided into several polyominoes. A polyomino is a shape made by joining one or more equal-sized squares edge to edge.

Every cell of the grid contains one positive integer. The placement is valid only if all of the following rules hold.

• In a polyomino of size k, each integer from 1 through k must appear exactly once.
• If the same number x appears more than once in the same row or in the same column, then any two such x cells must have at least x other cells between them. Equivalently, their row or column positions must differ by at least x + 1.

In this problem, every polyomino has size at most 8.

The first line contains the number of test cases T. (T <= 100)

For each test case, the first line contains two integers R and C. (4 <= R, C <= 15)

The next R lines each contain a string of length C describing the numbers written in the grid. Each character is d_i, where 1 <= d_i <= 8.

The next R lines each contain C integers describing which neighboring cells each cell is connected to. Call this R x C table descr. Each value satisfies 0 <= descr(r,c) <= 15.

The value descr(r,c) is determined by the directions in which cell (r,c) is connected to adjacent cells.

descr(r,c) = 0
if connected((r,c), (r-1,c)): descr(r,c) += 1  # UP
if connected((r,c), (r,c+1)): descr(r,c) += 2  # RIGHT
if connected((r,c), (r+1,c)): descr(r,c) += 4  # DOWN
if connected((r,c), (r,c-1)): descr(r,c) += 8  # LEFT

For example, a cell belonging to a polyomino of size 1 is not connected to any neighboring cell, so its value is 0. A cell connected to both the cell above and the cell below has value 5.

For each test case, print valid if the grid satisfies the rules, and print invalid otherwise.