The end of the world always has been a subject of controversy thru history, for example, in year 999 and in the 1999. Now there are persons that believe that the Mayan predicted a change in 2012, specifically in 21st December, 2012, some other speculate that the EoW will come with certain asteroid crashing onto Earth, or that planetary aligning has something to do with it....

At ACM (Association of Catastrophe Mitigation) they are 100% sure that the end might come with a Zombie Apocalypse, accordingly they are preparing with a Zombie Detection Mechanism, that it is some sort of radar. Right now the mechanism is on beta testing because is having errors identifying zombies. Sometimes it gives false positives measures. They have asked you, a wonderful programmer, to make a program that tells them if a lecture is right or not, basically you will be given two 2-D snapshots of zombies locations, let's call them the previous and the present snapshots, the zombies will be represented by a '*', while empty spaces will be represented by '.', your awesome program must tell if the present snapshot is a valid one, based on the previous one. A present snapshot is considered valid if:

1. It has no less zombies than the previous snapshot.
2. Every zombie in the previous snapshot could have moved only one square in each of the eight directions, or it is in the same square it was previously.

Input

The first line will have the dimensions of the snapshots, in the form of R C. (2 ≤ R, C ≤ 20)

Then R lines of C characters follow, describing the previous snapshot, then another set of R lines and C characters each line, that belongs to the present snapshot. The two snapshots are separated by a line with the character 'N'.

The last test case is followed by 0 0.

There will be at most 9 zombies in previous snapshot.

Output

For each test case print VALID, if the two snapshots correspond each other, NOT VALID otherwise.

Example

Input:
5 4
....
....
.*..
....
....
N
....
....
..*.
....
....
6 6
......
.*..*.
......
......
......
......
N
......
....*.
......
....*.
......
..*...
0 0

Output:
VALID
NOT VALID