← 返回题目列表

Codeforces · 1395/B

B. 博博尼乌下棋

中文机器翻译题面 查看原题

Boboniu 喜欢和他的员工下棋。众所周知,在国际象棋比赛中,没有任何员工能够击败老板,所以博博尼乌在任何一轮比赛中都没有输过。

您是他公司的新申请人。博博尼乌将用以下国际象棋问题来测试你:

考虑一个 $$$n\times m$$$ 网格(行的编号从 $$$1$$$ 到 $$$n$$$,列的编号从 $$$1$$$ 到 $$$m$$$)。你有一个棋子,它位于不在边界上的某个单元格 $$$(S_x,S_y)$$$ 上(即 $$$2 \le S_x \le n-1$$$ 和 $$$2 \le S_y \le m-1$$$)。

从单元格 $$$(x,y)$$$ 中,您可以将棋子移动到 $$$(x,y')$$$ ($$$1\le y'\le m, y' \neq y$$$) 或 $$$(x',y)$$$ ($$$1\le x'\le n, x'\neq x$$$)。换句话说,棋子像车一样移动。从单元格中,您可以移动到同一行或同一列上的任何单元格。

您的目标是访问每个单元格一次。你能找到解决办法吗?

请注意,路线中两个相邻单元格之间的路径上的单元格不计为已访问的单元格,并且不需要返回到起点。

输入

输入的唯一行包含四个整数 $$$n$$$、$$$m$$$、$$$S_x$$$ 和 $$$S_y$$$ ($$$3\le n,m\le 100$$$, $$$2 \le S_x \le n-1$$$, $$$2 \le S_y \le m-1$$$) — 的数量分别是行数、列数和棋子的初始位置。

输出

您应该打印 $$$n\cdot m$$$ 行。

第 $$$i$$$ 行应包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \leq x_i \leq n$$$, $$$1 \leq y_i \leq m$$$),表示您访问的第 $$$i$$$ 个单元格。您应该精确打印 $$$nm$$$ 对 $$$(x_i, y_i)$$$,它们应该涵盖所有可能的对 $$$(x_i, y_i)$$$,这样 $$$1 \leq x_i \leq n$$$, $$$1 \leq y_i \leq m$$$。

我们可以证明,在这些约束下,总是存在一个解决方案。如果有多个答案,请打印其中一个。

示例

输入 #1

3 3 2 2

输出 #1

2 2
1 2
1 3
2 3
3 3
3 2
3 1
2 1
1 1

输入 #2

3 4 2 2

输出 #2

2 2
2 1
2 3
2 4
1 4
3 4
3 3
3 2
3 1
1 1
1 2
1 3

注意

两个示例的可能路线: