CF43D.Journey

The territory of Berland is represented by a rectangular field n × m in size. The king of Berland lives in the capital, located on the upper left square (1, 1). The lower right square has coordinates (n, m). One day the king decided to travel through the whole country and return back to the capital, having visited every square (except the capital) exactly one time. The king must visit the capital exactly two times, at the very beginning and at the very end of his journey. The king can only move to the side-neighboring squares. However, the royal advise said that the King possibly will not be able to do it. But there is a way out — one can build the system of one way teleporters between some squares so that the king could fulfill his plan. No more than one teleporter can be installed on one square, every teleporter can be used any number of times, however every time it is used, it transports to the same given for any single teleporter square. When the king reaches a square with an installed teleporter he chooses himself whether he is or is not going to use the teleport. What minimum number of teleporters should be installed for the king to complete the journey? You should also compose the journey path route for the king.

伯兰德王国的领土由一个 $n \times m$ 的矩形区域表示。伯兰德国王居住在首都，位于左上角方格 $(1,\,1)$ 处；右下角方格的坐标为 $(n,\,m)$。某日，国王决定环游全国并最终返回首都，途中需恰好访问每个方格一次（首都除外）；首都则必须恰好访问两次——一次在旅程开始时，一次在旅程结束时。国王每次只能移动到与其当前所在方格共享一条边的相邻方格。

然而，皇家顾问指出：国王可能无法仅凭常规移动完成这一计划。但存在一种补救方案：我们可以在某些方格之间构建一套单向传送器系统，使得国王能够成功实现该计划。每个方格上至多安装一个传送器；每个传送器可被使用任意多次，但每次使用时，它总是将国王传送到预先指定的、对该传送器唯一确定的某个方格。当国王抵达一个装有传送器的方格时，他可自主决定是否启用该传送器。

问：为使国王能完成上述旅程，最少需要安装多少个传送器？此外，你还需构造出国王的一条可行路径。

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100, 2 ≤  n · m) — the field size. The upper left square has coordinates (1, 1), and the lower right square has coordinates of (n, m).

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 100$，且 $2 \leq n \cdot m$）——表示棋盘的尺寸。左上角方格的坐标为 $(1, 1)$，右下角方格的坐标为 $(n, m)$。

On the first line output integer k — the minimum number of teleporters. Then output k lines each containing 4 integers _x_1 _y_1 _x_2 _y_2 (1 ≤ _x_1, _x_2 ≤ n, 1 ≤ _y_1, _y_2 ≤ m) — the coordinates of the square where the teleporter is installed (_x_1, _y_1), and the coordinates of the square where the teleporter leads (_x_2, _y_2).

Then print nm + 1 lines containing 2 numbers each — the coordinates of the squares in the order in which they are visited by the king. The travel path must start and end at (1, 1). The king can move to side-neighboring squares and to the squares where a teleporter leads. Besides, he also should visit the capital exactly two times and he should visit other squares exactly one time.

第一行输出一个整数 $k$ —— 所需传送门的最少数量。随后输出 $k$ 行，每行包含四个整数 $x_1\ y_1\ x_2\ y_2$（满足 $1 \le x_1, x_2 \le n$，$1 \le y_1, y_2 \le m$），表示传送门安装位置的方格坐标 $(x_1, y_1)$ 以及该传送门通向的方格坐标 $(x_2, y_2)$。

然后输出 $nm + 1$ 行，每行包含两个数字 —— 表示国王所访问方格的坐标，按访问顺序排列。旅行路径必须起始并终止于 $(1, 1)$。国王可移动至相邻（上下左右）的方格，也可通过传送门直接到达其目标方格。此外，国王必须恰好两次访问首都（即 $(1,1)$），而其余每个方格则必须恰好访问一次。