CF43D Journey

你现在处于 $n\times m$ 的矩阵中 $(1,1)$ 这个点上。你现在的目标是走完全部点且不能走重复的点。你每一次只能移动 $1$ 格。 但是，你可以在迷宫中的任意一点放置一个传送门，这个传送门可以将你单向传送到一个传送门标记的点。现在求放置传送门次数最少的移动方案。

输入共 $1$ 行，输入 $n$ 和 $m$。

第一行输出传送门的最少放置个数 $k$。 接下来 $k$ 行，每行输出一组 $x_0,y_0,x_2,y_1$，表示有一个 $(x_0,y_0)\to(x_1,y_1)$ 的传送门。 接下来 $nm+1$ 行，每行输出此时所在的点的坐标。

对于 $100\%$ 的数据，保证 $1\le n,m\le100$，$n\times m>1$。 ## 提醒 $(1,1)$ 会在起始与末尾各出现一次！ --- Translated by [残阳如血](/user/726139)。