配点 : $600$ 点

問題文

縦横 $H \times W$ のチェス盤と $1$ 個のキングの駒があります。 チェス盤のマスのうち、上から $i$ 行目 $(1 \leq i \leq H)$ で左から $j$ 行目 $(1 \leq j \leq W)$ のマスを $(i, j)$ と表します。 キングは置かれているマスから周囲 $1$ マスに動かすことができます。より厳密には、チェス盤のマス目の組 $(i, j)$, $(k, l)$ が $\max(|i-k|,|j-l|) = 1$ を満たすとき、かつその時に限り $(i,j)$ に置かれているキングを $(k, l)$ に動かすことができます。

次の条件を満たすようにキングを縦横 $H \times W$ のチェス盤上で動かすことを「ツアー」と定めます。

• はじめ、$(1, 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)$ となるものを $1$ つ構成して出力してください。この問題の制約下において解は必ず存在することが証明できます。

制約

• $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$ 行目には $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)$ を終点とするツアーとなっています。 条件を満たすツアーは他にもいくつかあり、たとえば以下の $3$ つの移動が挙げられます。

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