Note that some solution requires complex conditional branches depending on, for example, whether the goal \((a, b)\) is on the boundary or not.

Here, in order to avoid complex case divisions, we will try to solve it recursively by boiling down the given problem to that of smaller sizes.

(1) If \(H = 2\)

We can construct the following tour.

Formally, the king is moved as

\((1, 1) \rightarrow (2, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow \cdots \rightarrow (1, b-1) \rightarrow (2, b-1) \rightarrow (3-a, b) \rightarrow\)

then as

\(\rightarrow (1, b+1) \rightarrow (1, b+2) \rightarrow \cdots \rightarrow (1, W) \rightarrow (2, W) \rightarrow (2, W-1) \rightarrow \cdots \rightarrow (2, b+1) \rightarrow (a, b)\).

(2) If \(H > 2\) and \(W = 2\)

We can swap the role of rows and columns so that it is boiled down to the “(1) If \(H = 2\)” case above.

(3) If \(H > 2\) and \(W>2\)

Divide into two cases by whether the goal \((a, b)\) is contained in the region \(S\) illustrated below.

In other words, let

\(S := \lbrace (1, 1), (2, 1) (3, 1), \ldots, (H, 1), (H, 2) \rbrace\),

and divide into the following cases depending on whether \((a, b) \in S\).

・ If \((a, b) \not\in S\)

If you move the king as > \((1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow \cdots \rightarrow (H, 1) \rightarrow (H, 2)\), it is then boiled down to the problem of “move the king from \((H,2)\) to \((a,b)\), visiting every other square.” Therefore, by removing the first column from the board and flipping it vertically, it is boiled down to the problem where \(W\) is decreased by \(1\).

・ If \((a, b) \in S\)

By swapping the roles of row and column, it is boiled down to the “If \((a, b) \not\in S\)” case above.

A sample code in C++ follows.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> P;

vector<P> solve(int h, int w, int a, int b)
{
	vector<P> ret;
	if(h == 2){
		for(int i = 1; i <= b-1; i++) ret.push_back(P(1, i)), ret.push_back(P(2, i));
		ret.push_back(P(3-a, b));
		for(int i = b+1; i <= w; i++) ret.push_back(P(1, i));
		for(int i = w; i >= b+1; i--) ret.push_back(P(2, i));
		ret.push_back(P(a, b));
	}
	else if(h > 2 && w == 2 || b == 1 || a == h && b == 2){
		ret = solve(w, h, b, a);
		for(auto &p : ret) swap(p.first, p.second);
	}
	else{
		for(int i = 1; i <= h; i++) ret.push_back(P(i, 1));
		vector<P> res = solve(h, w-1, h+1-a, b-1);
		for(auto &p : res) p.first = h+1-p.first, p.second++;
		ret.insert(ret.end(), res.begin(), res.end());
	}
	return ret;
}

int main(void)
{
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	vector<P> ans = solve(h, w, a, b);
	for(auto p : ans) cout << p.first << " " << p.second << endl;
	return 0;
}