P5372 [SNOI2019] 积木

有一块 $n$ 行 $m$ 列的网格板， $n,m$ 都是奇数。网格上平铺着一些 $1\times 2$ 的积木。积木可以旋转，不能重叠。这些积木共有 $\frac{nm-1}{2}$ 块，也就是说，网格板上只有一格的空位。 你可以做两种操作： 1. 将一块与空白格相邻（指有公共边）的积木旋转 $90^\circ$ 到空白格中； 2. 将一块与空白格积木相邻的积木平移至空白格中。 如图所示（被移动的积木颜色较浅）：  请你用以上两种操作将给定的网格板变换为指定的状态。

无

无

#### 数据范围与说明 你输出的操作序列长度不能超过 $8\times 10^6$ 。 对于所有数据， $1\leq n,m\leq 2000$ 。 - 对于 $10\%$ 的数据， $n,m\leq 3$ ； - 对于另外 $10\%$ 的数据， $n,m\leq 5$ ； - 对于另外 $20\%$ 的数据， $m=3$ ； - 对于另外 $20\%$ 的数据， $n,m\leq 50$ ； - 对于另外 $20\%$ 的数据， $n,m\leq 200$ ； - 对于余下 $20\%$ 的数据，无特殊限制。 #### SPJ 说明 参考 https://www.luogu.org/discuss/show/114298 ，感谢 @M_sea 的贡献。