P16118 [USTCPC 2026] Filling with Z-shape

There is an $m \times n$ grid, with coordinates indexed starting from $0$. Initially, every cell contains $-1$. In one operation, you may choose a "Z-shaped" region (see the picture; rotations and reflections are allowed), and negate all numbers in that region. Given $m, n$, determine whether there exists a sequence of operations that turns all numbers in the grid into $1$. If no such sequence exists, output `Impossible!`. 

The input contains two integers $m, n$ ($2\leq m,n\leq 2\times 10^5, 4\leq mn \le 2\times 10^5$), representing the number of rows and columns of the grid.

If a solution exists, output an operation sequence: on the first line output the number of operations $r$ ($0\leq r\leq 10^6$), then output $r$ lines, each containing $8$ integers, representing the coordinates of the four cells of the "Z-shape" (in the order $x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4$; the order of the four points can be arbitrary). If no solution exists, output `Impossible!`. If there are multiple solutions, output any one of them. It can be proven that if a valid solution exists, then there must exist a valid solution with $0\leq r \leq 10^6$.

Translated by ChatGPT 5