#include<bits/stdc++.h>
#include "puzzle.h"
#define LL int
#define SZ(x) ((LL)(x.size()))
#define all(x) (x).begin(),(x).end()
using namespace std;

inline void dmin(LL &x,LL y){if(x>y)x=y;return ;}
inline void dmax(LL &x,LL y){if(x<y)x=y;return ;}

#define cout cerr
#define pb push_back

namespace GenHelper{
#define ull unsigned long long
  ull seed=19260817ull;
  inline void Get(){seed^=(seed<<7);seed^=(seed>>11);seed^=(seed<<13);}
  inline ull Rand(){Get();return (seed^(seed<<32ull));}
}using GenHelper::Rand;
inline LL random(LL l,LL r){return (Rand()%(r-l+1)+l);}

const LL N = 1000+95 ;
LL n;vector<LL>P,ans;

#define PL pair<LL,LL>
#define mp make_pair
#define fir first
#define sec second

inline LL GET(vector<PL>vc){
  vector<LL>p=P;
  for(auto u:vc){
    //    cout<<" -> u.fir = "<<u.fir<<" u.sec = "<<u.sec<<endl;
    swap(p[u.fir],p[u.sec]);
  }
  //  cout<<" p : ";for(auto u:p)cout<<u<<" ";cout<<endl;
  return query(p);
}

LL X=-1,Y=-1;
inline bool __brute(LL x,LL y){//极其暴力的判断单点的 p[x] 是否等于 y ,错误率 0.0101 .
  for(LL TC=1;TC<=20;TC++){
    vector<LL>p(n);for(LL i=0;i<n;i++)p[i]=i;
    for(LL i=0;i<n;i++)swap(p[i],p[random(0,(n-1))]);
    for(LL i=0;i<n;i++)if(p[i]==y){swap(p[x],p[i]);break;}
    if(query(p)==0)return 0;
  }
  return 1;
}
inline bool brute(LL x,LL y){//判断单点 p[x] 是否等于 y
  if(X==-1)return __brute(x,y);
  //用一组正确的匹配强行拆解掉原有匹配
  vector<LL>p(n);for(LL i=0;i<n;i++)p[i]=i;
  for(LL i=0;i<n;i++)swap(p[i],p[random(0,(n-1))]);
  for(LL i=0;i<n;i++)if(p[i]==Y){swap(p[X],p[i]);break;}
  for(LL i=0;i<n;i++)if(p[i]==y){swap(p[x],p[i]);break;}
  LL k=query(p);swap(p[x],p[X]);LL _k=query(p);
  return ((k==_k+2)?(1):(0));
}

void solve(vector<PL>&vc,LL l,LL r,LL cnt){
  //  cout<<" -> l = "<<l<<" r = "<<r<<endl;
  if(!cnt)return ;
  //  cout<<" -> l = "<<l<<" r = "<<r<<" cnt = "<<cnt<<endl;
  if(l==r){
    //    cout<<" -> vc[l].fir = "<<vc[l].fir<<" P[vc[l].sec] = "<<P[vc[l].sec]<<" vc[l].sec = "<<vc[l].sec<<" P[vc[l].fir] = "<<P[vc[l].fir]<<endl;
    if(cnt==1){
      if(brute(vc[l].fir,P[vc[l].sec])){
	ans[vc[l].fir]=P[vc[l].sec];
	X=vc[l].fir;Y=P[vc[l].sec];
	//	cout<<" -> vc[l].fir = "<<vc[l].fir<<" P[vc[l].sec] = "<<P[vc[l].sec]<<endl;
      }
      else {
	ans[vc[l].sec]=P[vc[l].fir];
	X=vc[l].sec;Y=P[vc[l].fir];
	//	cout<<" -> vc[l].sec = "<<vc[l].sec<<" P[vc[l].fir] = "<<P[vc[l].fir]<<endl;
      }
    }
    else {
      //      cout<<" -> vc[l].fir = "<<vc[l].fir<<" P[vc[l].sec] = "<<P[vc[l].sec]<<endl;
      ans[vc[l].fir]=P[vc[l].sec];
      X=vc[l].fir;Y=P[vc[l].sec];
      //      cout<<" -> vc[l].sec = "<<vc[l].sec<<" P[vc[l].fir] = "<<P[vc[l].fir]<<endl;
      ans[vc[l].sec]=P[vc[l].fir];
    }
    return ;
  }
  LL mid=(l+r)>>1;
  vector<PL>tmp;for(LL i=l;i<=mid;i++)tmp.pb(vc[i]);
  LL cntl=GET(tmp);LL cntr=cnt-cntl;
  solve(vc,l,mid,cntl);solve(vc,mid+1,r,cntr);
  return ;
}

void play(LL _n_){
  n=_n_;if(n==1){check({0});return ;}
  P.resize(n);for(LL t=0;t<n;t++)P[t]=t;
  while(true){
    for(LL t=0;t<n;t++)swap(P[t],P[random(0,(n-1))]);
    //    cout<<" -> p = ";for(auto u:P)cout<<u<<" ";cout<<endl;
    if(!query(P))break;
  }
  //  cout<<" P " ;for(auto u:P)cout<<u<<" ";cout<<endl;
  
  vector<vector<PL>>vc;
  if(n&1){
    auto tr=[&](LL x){
	      if(x<1)x+=n;
	      if(x>n)x-=n;
	      return x;
	    };
    vc.resize(n);
    for(LL t=0;t<n;t++){
      vector<PL>p;
      for(LL i=1;i<=(n>>1);i++)p.pb(mp(tr((t+1)-i),tr((t+1)+i)));
      vc[t]=p;
    }
  }
  else {
    auto tr=[&](LL x){
	      if(x<1)x+=(n-1);
	      if(x>(n-1))x-=(n-1);
	      return x;
	    };
    vc.resize(n-1);
    for(LL t=0;t<n-1;t++){
      vector<PL>p;p.pb(mp(t+1,n));
      for(LL i=1;i<(n>>1);i++)p.pb(mp(tr((t+1)-i),tr((t+1)+i)));
      vc[t]=p;
    }
  }
  /*  for(LL t=0;t<SZ(vc);t++){
    cout<<"> t = "<<t<<" vc[t] : ";
    for(auto u:vc[t])cout<<" ("<<u.fir<<","<<u.sec<<") ";cout<<endl;
  }*/
  ans.resize(n);
  for(LL t=0;t<SZ(vc);t++){
    for(LL i=0;i<SZ(vc[t]);i++){vc[t][i].fir--;vc[t][i].sec--;}
    solve(vc[t],0,SZ(vc[t])-1,GET(vc[t]));
  }
  //  cout<<" -> ans : ";for(auto u:ans)cout<<u<<" ";cout<<endl;
  check(ans);return ;
}