Problem #3630 - ECNU Online Judge

单点时限: 1.0 sec

内存限制: 256 MB

There is a $n \times m$ chessboard. Queen’s position right now is $(x, y)$ .

Queen is the most powerful chess. It can be moved any number of unoccupied squares in a straight line vertically, horizontally, or diagonally (in all eight directions).

Bad Queen is a greedy queen. It wants to travel around all the blocks on the chessboard, but don’t want to take too many moves to make that happen. Please devise a route such that Bad Queen can visit all the blocks on the chessboard in exactly $n m - 1$ moves. The current position is considered as visited.

输入格式

The input contains four space-separated integers $n, m, x, y$ ( $1 \leq x \leq n \leq 100$ , $1 \leq y \leq m \leq 100$ , $n m > 1$ ).

输出格式

Output the move sequence in order. That is $n m - 1$ lines. Each line contains a coordinate $(x, y)$ , separated with space, which is the position after the move.

$x_{1} y_{1} x_{2} y_{2} ⋮ x_{n m - 1} y_{n m - 1}$

$(x_{i}, y_{i})$ must be a legal position on chessboard, which means $1 \leq x_{i} \leq n$ , $1 \leq y_{i} \leq m$ .

If there are multiple solutions available, you may output any of them.

样例

Input

3 3 1 1

Output

提示

Here is the route in the example. 0 is the starting position, and 1 to 8 are the visiting orders.

147 人解决，184 人已尝试。

163 份提交通过，共有 579 份提交。

3.1 EMB 奖励。

创建: 6 年，8 月前.

修改: 6 年，7 月前.

最后提交: 1 年，4 月前.

来源: EOJ Monthly 2018.8

construction

3630. Bad Queen

输入格式

输出格式

样例

提示

服务

开源

关于我们