tioj 1004

#include <bits/stdc++.h>
using namespace std;

/*
1 1 1 1 1
1 0 1 1 1
1 0 1 0 1
0 0 1 0 1
0 0 1 0 0
*/

int cnt = 0;

int killer(int pos, int n, vector<int> v){
    for( auto i : v ){
        cout<<i<<' ';
    }
    cout<<endl;
    
    if( cnt == 1 ) return 0;
    
    if( pos >= n ) return killer(0, n, v);
    
    if( pos == n-1 ){
        if( v[0] == 0 ) return killer(0, n, v);
        v[0] = 0;
        cnt-=1;
        return 0;
    }
    
    if( v[pos] == 0 ) return killer(pos+1, n, v);
    
    v[pos+1] = 0;
    cnt-=1;
    return killer(pos+2, n, v);
}

int main(){
    int n; cin>>n;
    cnt = n;
    vector<int> v(n, 1);
    
    killer(0, n, v);
    
    for(int i=0; i<n; i++){
        if( v[i] == 1 ) cout<<i+1<<endl;
    }
}