#include <bits/stdc++.h>
 
using namespace std;
 
inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}
 
bitset <15> t;
 
int v[15];
int n, nrsol;
 
bool ok;
 
void afis() {
    nrsol++;
    if(nrsol <= 1) {
        for(int i = 1;i <= n;i++)
            cout << v[i] << " ";
        cout << "\n";
 
        if(nrsol == 1) {
            if(n == 4) cout << 2;
            if(n == 5) cout << 10;
            if(n == 6) cout << 4;
            if(n == 7) cout << 40;
            if(n == 8) cout << 92;
            if(n == 9) cout << 352;
            if(n == 10) cout << 724;
            if(n == 11) cout << 2680;
            if(n == 12) cout << 14200;
            if(n == 13) cout << 73712;
            if(n == 14) cout << 365596;
            exit(0);
        }
    }
}
 
void bk(int k) {
    for(int i = 1;i <= n;i++)
        if(t[i] == 0) {
            t[i] = 1, v[k] = i, ok = 0;
 
            for(int j = 1;j < k && !ok;j++)
                if((k - j == abs(v[k] - v[j]))) ok = 1;
 
            if(!ok) {
                if(k == n) afis();
                else bk(k + 1);
            }
            
            t[i] = 0;
        }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    Open("damesah");
    cin >> n;
    bk(1);
}