当前没有测试数据。

H - 国王的行程

得分：600分

问题描述

给定一个 $H \times W$ 的国际象棋棋盘，有 $H$ 行 $W$ 列，以及一个君主。

用 $(i, j)$ 表示从上到下的第 $i$ 行、从左到右的第 $j$ 列的方格。

君主可以在任何方向上移动一个方格。具体来说，君主在 $(i,j)$ 可以移动到 $(k,l)$，当且仅当 $\max(|i-k|,|j-l|) = 1$。

一个“旅行”是将国王放在 $H \times W$ 的棋盘上移动的过程。

• 首先把国王放在 $(1, 1)$ 上。然后移动国王，使其每个方格恰好被放置一次。

举个例子，当 $H = 2, W = 3$ 时，$(1,1) \to (1,2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1)$ 就是一个有效的旅行。

给定一个不是 $(1, 1)$ 的方格 $(a, b)$。构造一条以 $(a,b)$ 结尾的旅行并打印出来。可以证明，在本问题的约束条件下，一定存在一个解。

约束条件

• $2 \leq H \leq 100$
• $2 \leq W \leq 100$
• $1 \leq a \leq H$
• $1 \leq b \leq W$
• $(a, b) \neq (1, 1)$
• 输入中的所有值都是整数。

输入

输入的格式如下：

$H$ $W$ $a$ $b$

输出

打印 $HW$ 行。第 $i$ 行应该包含国王放置在 $(h_i, w_i)$ 上的方格，格式如下：

$h_i$ $w_i$

注意，第一行应该包含 $(1, 1)$，第 $HW$ 行应该包含 $(a, b)$。

示例

输入1

3 2 3 2

输出1

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

国王依次移动 $(1, 1) \to (1, 2) \to (2, 1) \to (2, 2) \to (3, 1) \to (3, 2)$，这是一个以 $(3, 2)$ 结尾的旅行。还有其他一些合法的旅行，其中三个列举如下：

• $(1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2)$
• $(1, 1) \to (2, 1) \to (1, 2) \to (2, 2) \to (3, 1) \to (3, 2)$
• $(1, 1) \to (2, 2) \to (1, 2) \to (2, 1) \to (3, 1) \to (3, 2)$