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.
