Listen everyone, who wants to prove the algorithm to this problem!
See the solution of the problem 3 from IMO34 (International Mathematical Olympiad, year 1993).
The rectangle in that problem is n*n (not m*n), but it isn't important.
And the case 1*n is clear, I think.

The problem statement in the problem set for IMO34 is somewhat better. Definitely worth reading.