#include<iostream>
#include<cstdlib>
#include<vector>

using namespace std;

vector<vector<int>>result;
vector<int>want;
int ans = 0, n;

bool isLimit(vector<vector<int>>& chess, int x, int y, int n)
{
	//竖
	for (int i = 0; i < x; i++) {
		if (chess[i][y] == 1) return false;
	}
	//45
	for (int i = x - 1, j = y + 1; j < n && i >= 0; j++, i--) {
		if (chess[i][j] == 1) return false;
	}
	//135
	for (int i = x - 1, j = y - 1; j >= 0 && i >= 0; j--, i--) {
		if (chess[i][j] == 1) return false;
	}
	return true;
}
void backtracking(vector<vector<int>>& chess, int row, int n)
{
	if (row == n) {
		ans++;
		if (ans <= 3) {
			result.push_back(want);
		}
		return;
	}
	for (int col = 0; col < n; col++) {
		if (isLimit(chess, row, col, n)) {
			chess[row][col] = 1;
			if(ans<=3) want.push_back(col + 1);

			backtracking(chess, row + 1, n);

			chess[row][col] = 0;
			if(ans<=3) want.pop_back();
		}
	}
}
int main()
{
	cin >> n;
	vector<vector<int>>chess(n,vector<int>(n,0));
	backtracking(chess, 0, n);
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j != result[0].size(); j++) {
			cout << result[i][j] << " ";
		}
		cout << endl;
	}
	cout << ans << endl;
	return 0;
}