国王的巡游

题目描述

有一个 $H$ 行 $W$ 列的棋盘和一枚国王。

用 $(i, j)$ 表示从上数第 $i$ 行 $(1 \le i \le H)$、从左数第 $j$ 列 $(1 \le j \le W)$ 的格子。

国王可以向任意方向移动一格。形式化地说,位于 $(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)$ 结束的巡游并输出它。可以证明,在本题的约束下解总是存在。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出 $HW$ 行。第 $i$ 行按以下格式输出国王第 $i$ 次所在的格子 $(h_i, w_i)$。

$h_i$ $w_i$

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

样例

3 2 3 2

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)$

数据范围

• $2 \le H \le 100$
• $2 \le W \le 100$
• $1 \le a \le H$
• $1 \le b \le W$
• $(a, b) \neq (1, 1)$
• 输入均为整数

提示

答案不唯一,输出任意合法解即可。