Lát gạch cổ điển đen trắng

Time limit: 1.0s , Memory limit: 256M , Points: 25 (partial)

Nhà Bi lát gạch kiểu cổ điển đen trắng với mặt sàn kích thước $M \times N$ ~M \times N~, gọi ô ở dòng thứ $r$ ~r~ và cột thứ $c$ ~c~ là ô $(r,c)$ ~(r,c)~, đánh chỉ số dòng và cột từ số $1$ ~1~. Bi lát theo quy tắc:

Có chính xác $N$ ~N~ ô màu đen.
Ô $(1,1)$ ~(1,1)~ là màu đen.
Nếu ô $(r, a)$ ~(r, a)~ và $(r, b)$ ~(r, b)~ là màu đen thì ô $(r, k)$ ~(r, k)~ là màu đen với $a < k < b$ ~a < k < b~.
Nếu ô $(r, c)$ ~(r, c)~ là màu đen thì ô $(r-1, c)$ ~(r-1, c)~ nếu ô tồn tại sẽ là màu đen.
Nếu ô $(r, c)$ ~(r, c)~ là màu đen và không có $k$ ~k~ nào thỏa $k < c$ ~k < c~ sao cho ô $(r, k)$ ~(r, k)~ là màu đen thì ô $(r+1, c)$ ~(r+1, c)~ nếu tồn tại thì nó sẽ có màu trắng.
Hai cách lát gạch là khác nhau nếu có một ô của cách lát thứ nhất màu trắng và màu đen đối với cách lát thứ hai.