Given three grid pictures, find the translation of the second that makes the XOR of the first two match the third, up to translation.
Hard8ImplementationString matchingBrute forceHash mapNo attempts yetTime limit2sMemory limit512 MBKevin and Kimberly each have freckles on their forehead.
Both of them drew a picture of their own freckles on a sheet of paper. A picture is a rectangle of cells, and every cell either has a freckle or has no freckle.
They joke that once they grow up, marry and have a child, the child's freckle picture comes out of the following procedure. Slide the two pictures over each other by a parallel translation, and then in every cell the child has a freckle exactly when one of the two parents has a freckle at that position and the other does not.
You are given the two pictures and the picture they want for the child. Decide whether some parallel translation produces that picture, and find the translation.
Two pictures are the same when one of them can be moved by a parallel translation so that its freckles land exactly on the freckles of the other. Empty rows and columns around the freckles do not matter.
The first line contains two integers h1 and w1 (1≤h1,w1≤1000), the height and the width of Kevin's picture. Each of the next h1 lines contains w1 characters * and .. The character * means that the cell has a freckle, and . means that it does not.
Kimberly's picture follows in the same format. Its height h2 and width w2 obey the same limits.
The picture they want for the child follows last, in the same format. Its height h3 and width w3 obey the same limits.
Each of the three pictures has at least one freckle.
Print YES on the first line if the desired picture can be produced, and NO otherwise.
If it can, print two integers x and y on the second line. Overlay the two parent pictures so that their upper left corners coincide, move Kimberly's picture x cells to the right (a negative x moves it to the left) and y cells down (a negative y moves it up), and then apply the procedure above. The resulting freckle pattern must coincide with the desired picture after a parallel translation.
If several pairs (x,y) work, print the one with the smallest x, and among those the one with the smallest y.