Problem Description

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!.

Input Format

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.

Output Format

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$.

2 4

4
0 0 0 1 1 1 1 2
1 0 1 1 0 1 0 2
1 3 0 1 1 2 0 2
1 1 1 2 0 2 0 3

2 5

Impossible!

Hint

Translated by ChatGPT 5