#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;
namespace Solve1{
int to[5][10],id[10];
void add(vector<int> i,int z){
to[z][i[0]]=i[1];
to[z][i[1]]=i[0];
}
vector<int> solve1(){
vector<vector<int>> rlt1=shuffle({{1,2},{3,4},{5,6}});
vector<vector<int>> rlt2=shuffle({{1,3},{2,4},{5,6}});
vector<vector<int>> rlt3=shuffle({{1,5},{3,4},{2,6}});
vector<vector<int>> rlt4=shuffle({{1,6},{3,2},{5,4}});
for(auto i:rlt1) add(i,1);
for(auto i:rlt2) add(i,2);
for(auto i:rlt3) add(i,3);
for(auto i:rlt4) add(i,4);
vector<int> ret(6,0);
for(int i=1;i<=6;i++){
if(to[2][i]==to[1][i]) id[i]=3;
else if(to[3][i]==to[1][i]) id[i]=2;
else id[i]=1;
}
for(int i=1;i<=6;i++){
if(id[i]==1){
if(id[to[4][i]]==3) ret[0]=i;
else ret[1]=i;
}
else if(id[i]==2){
if(id[to[4][i]]==1) ret[2]=i;
else ret[3]=i;
}
else{
if(id[to[4][i]]==2) ret[4]=i;
else ret[5]=i;
}
}
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++;
//cout<<cnt3<<endl;
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);
/*for(int i:rlt1[0]) cout<<i<<" ";
cout<<endl;
for(int i:rlt1[1]) cout<<i<<" ";
cout<<endl;
for(int i:rlt2[0]) cout<<i<<" ";
cout<<endl;
for(int i:rlt2[1]) cout<<i<<" ";
cout<<endl;
for(int i:rlt3[0]) cout<<i<<" ";
cout<<endl;
for(int i:rlt3[1]) cout<<i<<" ";
cout<<endl;*/
pair<int,int> dif1=find(rlt1,rlt2),dif2=find(rlt1,rlt3);
//cout<<dif1.first<<" "<<dif1.second<<endl;
//cout<<dif2.first<<" "<<dif2.second<<endl;
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;
//cerr<<val<<endl;
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;
}
}
vector<int> solve(int N, int B, int K, int Q, int ST) {
if(K==2) return Solve1::solve1();
return Solve2::solve2(N);
}
