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

typedef long long ll;
const int N=500003;
typedef array<int,2> Nod; 
#define pb push_back


int op,n,m,sum;
vector<Nod>a;
bool ban[N];
vector<int>res,cur,ve[N];
mt19937 rd(random_device{}());
#define mi ((l+r)>>1)

int Cou(vector<int>A)
{
	if(op)A.pop_back();
	return query(A);
}
void Sol(int l,int r,int cnt)
{
	if(!cnt)return;
	if(l==r)
	{
	    ve[a[l][0]].pb(a[l][1]);
		ve[a[l][1]].pb(a[l][0]);
		swap(cur[a[l][0]],cur[a[l][1]]);
		sum+=cnt;return;
	}
	vector<int>now=res;
	for(int i=l;i<=mi;i++)swap(now[a[i][0]],now[a[i][1]]);
	int lc=Cou(now);
	Sol(l,mi,lc);Sol(mi+1,r,cnt-lc); 
}
void play(int _n)
{
	n=_n;op=n&1;
	if(op)n++;
	m=n/2;res.resize(n);
	iota(res.begin(),res.end(),1);shuffle(res.begin(),res.end()-op,rd);
	while(Cou(res))shuffle(res.begin(),res.end()-op,rd);
	vector<int>id(n,0);iota(id.begin(),id.end(),0);shuffle(id.begin(),id.end(),rd);
	for(int t=0;t+1<n;t++)
	{
		a.clear();vector<int>vis(n,0);int k1=-1,k2=-1;m=0;
		for(int i=0,j=0;i<n;i++)if(2*id[i]%(n-1)!=t&&(j=(t-id[i]+n-1)%(n-1))>id[i])
		{
		    if(ve[id[i]].size()<2&&ve[j].size()<2&&max(id[i],j)<n-op)a.pb({id[i],j}),m++;
			vis[id[i]]=vis[j]=1;
		}
		for(int i=0;i<n;i++)if(!vis[i])k1==-1?k1=i:k2=i;
		if(ve[k1].size()<2&&ve[k2].size()<2&&max(k1,k2)<n-op)a.pb({k1,k2}),m++;
		vector<int>o=res;
		for(Nod t:a)swap(o[t[0]],o[t[1]]);
		cur=res;
		if(m)Sol(0,m-1,Cou(o));
		if(sum==n)break;
	}
	vector<int>ans=res;
	for(int i=0;i<n-op;i++)if(!ban[i])
	{
		if((int)ve[i].size()==1)
		{
			ban[i]=ban[ve[i][0]]=1;
			swap(ans[i],ans[ve[i][0]]);continue;
		}
		vector<int>now;now.pb(i);ban[i]=1;
		for(int j=ve[i][0],las=i;;)
		{
			now.pb(j);ban[j]=1;las=j;
			if(!ban[ve[j][0]])j=ve[j][0];
			else if(!ban[ve[j][1]])j=ve[j][1];
			if(j==las)break;
		}
		vector<int>cur=res;cur[now[0]]=res[now.back()];
		for(int j=1;j<(int)now.size();j++)cur[now[j]]=res[now[j-1]];
		int x=Cou(cur);
		if(x)
		{
			for(int j=0;j<(int)now.size();j++)ans[now[j]]=cur[now[j]];
		}
		else
		{
			for(int j=0;j+1<(int)now.size();j++)ans[now[j]]=res[now[j+1]];
			ans[now.back()]=res[now[0]]; 
		}
	}
	if(op)ans.pop_back();
	check(ans);
}