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 ≤ n, m ≤ 100$，$2 ≤ n · 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$ 行，每行包含 4 个整数 $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$ 行，每行包含 2 个数字 —— 表示国王按访问顺序经过的各个方格的坐标。整个路径必须起始并终止于 $(1, 1)$。国王可以移动至相邻的上下左右四个方向的方格，以及传送门所指向的方格。此外，国王必须恰好访问首都（即 $(1,1)$）两次，而其余每个方格必须恰好访问一次。