/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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) を出力する必要がある点に注意せよ。
入力例 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) を終点とするツアーとなっています。
条件を満たすツアーは他にもいくつかあり、たとえば以下の 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)
Score : 600 points
Problem Statement
We have an H \times W chessboard with H rows and W columns, and a king.
Let (i, j) denote the square at the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W).
The king can move one square in any direction. Formally, the king on (i,j) can move to (k,l) if and only if \max(|i-k|,|j-l|) = 1.
A tour is the process of moving the king on the H \times W chessboard as follows.
- Start by putting the king on (1, 1). Then, move the king to put it on each square exactly once.
For example, when H = 2, W = 3, going (1,1) \to (1,2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) is a valid tour.
You are given a square (a, b) other than (1, 1). Construct a tour ending on (a,b) and print it. It can be proved that a solution always exists under the Constraints of this problem.
Constraints
- 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)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W a b
Output
Print HW lines. The i-th line should contain the i-th square (h_i, w_i) the king is put on, in the following format:
h_i w_i
Here, note that the 1-st line should contain (1, 1), and the HW-th line should contain (a, b).
Sample Input 1
3 2 3 2
Sample Output 1
1 1 1 2 2 1 2 2 3 1 3 2
The king goes (1, 1) \to (1, 2) \to (2, 1) \to (2, 2)\to (3, 1) \to (3, 2), which is indeed a tour ending on (3, 2).
There are some other valid tours, three of which are listed below.
- (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)