Big Yuer was boring at home during his winter vacation, so he started to play “Find the Difference with beautiful girls” in QQgame.
However, experts are all over the Internet! Big Yuer was beaten again and again.
The evil inside his body began to grow, he decided to make a cheater (matlab version), and he suddenly had a far sight.
This is the working cheater, and the highlighted ones are the differences.
However, he encountered some problems, which need your help.
Suppose two pictures are N*M integer matrix, we define “Trouble Rectangle” between this two as these rectangles: First, the different pixel between them must be in some “Trouble Rectangle”; second, there might be some same pixels inside a “Trouble Rectangle”, but the pixels of the outer boundary must be same in two pictures (the outer boundary means the frame “Trouble Rectangle” produces when expanding 1 pixel larger, except those out side the picture); next, a “Trouble Rectangle” cannot be included in any other “Trouble Rectangle” and cannot be intersect or adjacent to any other “Trouble Rectangle”; at last, each “Trouble Rectangle” must be unable to break down into smaller “Trouble Rectangles”.
Take two 4*4 pictures as example:
In this picture, there are two “Trouble Rectangles”, shown in below.
We cannot take (2,2)-(2,2) as a “Trouble Rectangle” because its outer boundary in two pictures is not same, also we cannot take (1,1)-(2,4) as “Trouble Rectangle” because it can break down into (1,1)-(2,2) and (1,4)-(2,4).
Take a 5*5 one as another example.
There is only one “Trouble Rectangle”, shown in the red line below.
Because (3,3)-(3,3) is included in (1,1)-(5,5), so it’s not a “Trouble Rectangle”.