First, observe that we can get rid of all SAVE and LOAD commands with ~\mathcal O(M)~ time complexity. We process the sequence of commands in reverse order, starting from the last one down to the first one. Whenever a LOAD command is to be processed, we ignore all commands between this command and the corresponding SAVE command. With this approach, we obtain an equivalent sequence of commands which consists of only PAINT commands.

This problem can now be solved using a sweep-line algorithm. Traversing the painting row by row, we keep two tournament trees; a red one and a white one, for convenience. The red tree will contain the checkerboard patterns in which even squares are painted in the current row, while the white tree will contain the patterns in which odd squares are painted in the current row. As we traverse rows, we swap those two trees before advancing to the next row. The tree nodes will contain the sets of patterns which cover the corresponding intervals, sorted by the time of painting.

Note that insertion and removal of a pattern has ~\mathcal O(\log N \times \log M)~ time complexity, while a query for any square has ~\mathcal O(\log N)~ time complexity, which yields the total time complexity of ~\mathcal O(N^2 \log N + M \log N \log M)~.

Alternatively, the task can be solved with the union-find algorithm, in time complexity ~\mathcal O(NM)~. This is left as an exercise for the reader.