Problem D: Ripple Effect

Check if a solution to a Ripple Effect puzzle is valid.

Ripple Effect is played on a rectangular grid divided into polyominoes. A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge.

The solver must place one positive integer into each cell of the grid - some of which may be given in advance - according to these rules:

In this problem polyominoes will be of size at most 8.

Input Format

The input starts with a line containing an integer T (T <= 100), the number of test cases.
Each test case starts with two integers on a line, R and C (4<=R,C<=15).
R lines follow, each containing a string of C digits d_i(1<=d_i<=8), the description of the solution.

Next R lines will contain C integers (RxC table, we will call it "descr"), each describing the corresponding cell in the puzzle (0<=descr(r,c)<=15).
The value of descr(r,c) is determined by the values of connections with neighbouring cells, in the following manner:

 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 polyomino of size 1 (single square not connected to others) will have the value of 0 and a square that is connected only to the squares above and below will have the value of 5.

See sample input for clarification.

Output Format

For each test case print either "valid" or "invalid" on a single line.

Sample Input

2
6 6
241321
312432
131243
423121
214312
141231
2 12 4 4 6 8
4 5 1 5 5 4
5 1 0 5 1 5
3 8 4 1 4 1
2 10 9 2 9 4
0 2 10 10 8 1
6 6
421321
312432
131243
423121
214312
141231
2 12 4 4 6 8
4 5 1 5 5 4
5 1 0 5 1 5
3 8 4 1 4 1
2 10 9 2 9 4
0 2 10 10 8 1

Sample Output

valid
invalid

Darko Aleksic
ACPC 2012