#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;
namespace Solve1{
int to[5][1005];
void get(vector<vector<int>> rlt,int id){
for(vector<int> i:rlt) to[id][i[0]]=i[1],to[id][i[1]]=i[0];
}
vector<int> solve1(int n){
vector<vector<int>> tmp(0);
for(int i=1;i<=n;i+=2) tmp.push_back({i,i+1});
vector<vector<int>> rlt=shuffle(tmp);
get(rlt,1);
tmp.clear();
for(int i=2;i<n;i+=2) tmp.push_back({i,i+1});
tmp.push_back({n,1});
rlt=shuffle(tmp);
get(rlt,2);
tmp.clear(),tmp.push_back({1,3}),tmp.push_back({2,4});
for(int i=5;i<=n;i+=2) tmp.push_back({i,i+1});
rlt=shuffle(tmp);
get(rlt,3);
tmp.clear(),tmp.push_back({2,4}),tmp.push_back({3,5});
for(int i=6;i<n;i+=2) tmp.push_back({i,i+1});
tmp.push_back({n,1});
rlt=shuffle(tmp);
get(rlt,4);
vector<int> ret(0);
int st=0;
for(int i=1;i<=n;i++) if(to[3][i]!=to[1][i]&&to[4][i]==to[2][i]){
st=i;ret.push_back(i);break;
}
st=to[1][st],ret.push_back(st);
for(int i=2;i<=n/2;i++){
st=to[2][st],ret.push_back(st);
st=to[1][st],ret.push_back(st);
}
return ret;
}
}
namespace Solve2{
int tag[1005];
int lazy1[1005],lazy2[1005],rnk[10000];
pair<int,int> find(vector<vector<int>> x,vector<vector<int>> y){
for(int i:x[0]) tag[i]++;
for(int i:y[0]) tag[i]+=2;
int cnt3=0;
for(int i=1;i<=1000;i++) if(tag[i]==3) cnt3++;
if(cnt3==int(x[0].size())-1){
pair<int,int> ret={0,0};
for(int i=1;i<=1000;i++) if(tag[i]==2) ret.first=i;
for(int i=1;i<=1000;i++) tag[i]=0;
for(int i:x[1]) tag[i]++;
for(int i:y[1]) tag[i]+=2;
for(int i=1;i<=1000;i++) if(tag[i]==2) ret.second=i;
for(int i=1;i<=1000;i++) tag[i]=0;
return ret;
}
else{
for(int i=1;i<=1000;i++) tag[i]=0;
pair<int,int> ret={0,0};
for(int i:x[0]) tag[i]++;
for(int i:y[1]) tag[i]+=2;
for(int i=1;i<=1000;i++) if(tag[i]==2) ret.first=i;
for(int i=1;i<=1000;i++) tag[i]=0;
for(int i:x[1]) tag[i]++;
for(int i:y[0]) tag[i]+=2;
for(int i=1;i<=1000;i++) if(tag[i]==2) ret.second=i;
for(int i=1;i<=1000;i++) tag[i]=0;
return ret;
}
}
void getlazy(vector<vector<int>> ori,vector<vector<int>> tun,int val,int bit){
bool flag=0;
for(int i:ori[0]) if(i==1) flag=1;
if(flag) for(int i:ori[0]) lazy1[i]+=bit;
else for(int i:ori[1]) lazy1[i]+=bit;
flag=0;
for(int i:tun[0]) if(i==val) flag=1;
if(flag) for(int i:tun[0]) lazy2[i]+=bit;
else for(int i:tun[1]) lazy2[i]+=bit;
}
vector<int> solve2(int n){
int len=n/2;
vector<vector<int>> tmp(2,vector<int>(0));
for(int i=1;i<=len;i++) tmp[0].push_back(i);
for(int i=len+1;i<=n;i++) tmp[1].push_back(i);
vector<vector<int>> rlt1=shuffle(tmp);
tmp[0].clear(),tmp[1].clear();
tmp[0].push_back(len+1),tmp[1].push_back(1);
for(int i=2;i<=len;i++) tmp[0].push_back(i);
for(int i=len+2;i<=n;i++) tmp[1].push_back(i);
vector<vector<int>> rlt2=shuffle(tmp);
tmp[0].clear(),tmp[1].clear();
tmp[0].push_back(n),tmp[1].push_back(1);
for(int i=2;i<=len;i++) tmp[0].push_back(i);
for(int i=len+1;i<n;i++) tmp[1].push_back(i);
vector<vector<int>> rlt3=shuffle(tmp);
pair<int,int> dif1=find(rlt1,rlt2),dif2=find(rlt1,rlt3);
int val=0;
if(dif1.first==dif2.first) val=dif1.first;
else if(dif1.first==dif2.second) val=dif1.first;
else if(dif1.second==dif2.first) val=dif1.second;
else if(dif1.second==dif2.second) val=dif1.second;
tmp[0].clear(),tmp[1].clear();
for(int i=1;i<=len;i++) tmp[0].push_back(i);
for(int i=len+1;i<=n;i++) tmp[1].push_back(i);
getlazy(tmp,rlt1,val,1);
for(int bit=1;bit<=len;bit<<=1){
tmp[0].clear(),tmp[1].clear();
for(int i=1;i<=len;i++){
if(i&bit) tmp[0].push_back(i),tmp[1].push_back(i+len);
else tmp[1].push_back(i),tmp[0].push_back(i+len);
}
vector<vector<int>> rltnow=shuffle(tmp);
getlazy(tmp,rltnow,val,bit<<1);
}
for(int i=1;i<=n;i++) rnk[lazy2[i]]=i;
vector<int> ret(0);
for(int i=1;i<=n;i++) ret.push_back(rnk[lazy1[i]]);
return ret;
}
}
namespace Solve3{
struct Node{
int st,orist;
vector<int> member;
}s[1005];
int f2t1[1005],f1t2more[1005],tag[1005];
void init(vector<vector<int>> rlt1,vector<vector<int>> rlt2,int n,int B,int K){
for(int i=0;i<B;i++){
memset(tag,0,sizeof tag);
for(int p:rlt1[i]) tag[p]++;
for(int j=0;j<B;j++){
for(int p:rlt2[j]) tag[p]+=2;
int cnt=0;
for(int p=1;p<=n;p++) if(tag[p]==3) cnt++;
if(cnt==K-1){
f2t1[j]=i;
for(int p=1;p<=n;p++){
if(tag[p]==1) s[i].st=p;
else if(tag[p]==2) f1t2more[i]=p;
else if(tag[p]==3) s[i].member.push_back(p);
}
break;
}
for(int p:rlt2[j]) tag[p]-=2;
}
}
}
void getorist(vector<vector<int>> rlt2,vector<vector<int>> rlt3,int n,int B,int K){
int id=0;
for(int i=0;i<B;i++){
bool flagg=1;
for(int j=0;j<B&&flagg;j++){
memset(tag,0,sizeof tag);
for(int p:rlt2[i]) tag[p]++;
for(int p:rlt3[j]) tag[p]--;
bool flag=1;
for(int p=1;p<=n;p++) if(tag[p]) flag=0;
if(flag) flagg=0;
}
if(!flagg){
id=i;
break;
}
}
id=f2t1[id];
for(int i=0;i<B;i++){
s[id].orist=i,id=f1t2more[id];
for(int j=0;j<B;j++) if(s[j].st==id){
id=j;break;
}
}
}
int belongid[1005],toptag[1005],val[1005];
vector<int> solve(int n,int B,int K){
vector<vector<int>> tmp(B,vector<int>(0));
for(int i=0;i<B;i++) for(int j=K;j>=1;j--) tmp[i].push_back(j+i*K);
vector<vector<int>> rlt1=shuffle(tmp);
tmp[0].back()+=K,tmp[1].back()-=K;
vector<vector<int>> rlt3=shuffle(tmp);
for(int i=0;i<B;i++){
tmp[i].clear(),tmp[i].push_back((i+1)%B*K+1);
for(int j=2;j<=K;j++) tmp[i].push_back(j+i*K);
}
vector<vector<int>> rlt2=shuffle(tmp);
init(rlt1,rlt2,n,B,K);
getorist(rlt2,rlt3,n,B,K);
sort(s,s+B,[&](const Node &x,const Node &y){return x.orist<y.orist;});
//for(int i=0;i<B;i++){
// cout<<s[i].st<<" "<<s[i].orist<<endl;
// for(int j:s[i].member) cout<<j<<" ";
// cout<<endl;
//}
for(int i=0;i<B;i++){
toptag[s[i].st]=1,belongid[s[i].st]=i;
for(int j:s[i].member) belongid[j]=i;
}
for(int bit=1;bit<=K;bit*=B){
for(int i=0;i<B;i++){
tmp[i].clear();
tmp[i].push_back(i*K+1);
}
for(int i=0;i<B;i++){
for(int j=2;j<=K;j++){
int p=(i+(j/bit)%B)%B;
tmp[p].push_back(j+i*K);
}
}
vector<vector<int>> rlt=shuffle(tmp);
for(int i=0;i<B;i++){
int nowid=0;
for(int j:rlt[i]) if(toptag[j]){
nowid=belongid[j];break;
}
for(int j:rlt[i]) if(!toptag[j])
val[j]+=bit*((nowid+B-belongid[j])%B);
}
}
vector<int> ret(0);
for(int i=0;i<B;i++){
sort(s[i].member.begin(),s[i].member.end(),[&](const int &x,const int &y){
return val[x]<val[y];
});
ret.push_back(s[i].st);
for(int j:s[i].member) ret.push_back(j);
}
//for(int i:ret) cout<<i<<" "<<val[i]<<endl;
//cout<<endl;
return ret;
}
}
vector<int> solve(int N, int B, int K, int Q, int ST) {
if(K==2) return Solve1::solve1(N);
if(B==2) return Solve2::solve2(N);
return Solve3::solve(N,B,K);
}
