3630. Bad Queen

单点时限: 1.0 sec

内存限制: 256 MB

There is a chessboard. Queen’s position right now is .

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 moves. The current position is considered as visited.

输入格式

The input contains four space-separated integers (, , ).

输出格式

Output the move sequence in order. That is lines. Each line contains a coordinate , separated with space, which is the position after the move.

must be a legal position on chessboard, which means , .

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

样例

Input
3 3 1 1
Output
3 3
1 3
2 3
2 1
3 1
2 2
1 2
3 2

提示

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

142 人解决,178 人已尝试。

155 份提交通过,共有 560 份提交。

6.7 EMB 奖励。

创建: 11 月,3 周前.

修改: 11 月,2 周前.

最后提交: 2 月前.

来源: EOJ Monthly 2018.8

题目标签