#include "shuffle.h"
#include<bits/stdc++.h>
using namespace std;
#define inf 5e18
#define nl '\n'
#define vi vector<int>
#define vvi vector<vi>
int n, b, k;
vector<int> solve1(){
vvi qry1(b), qry2(b);
vvi res1, res2, res3, res4;
vi p1(n+1), p2(n+1), p3(n+1), p4(n+1);
for(int i=2, j=0; i<=n; i+=2, j++) qry1[j] = {i-1, i};
res1 = shuffle(qry1);
for(auto &v : res1){
p1[v[0]] = v[1];
p1[v[1]] = v[0];
}
for(int i=3, j=0; i<=n; i+=2, j++) qry2[j] = {i-1, i};
qry2[b-1] = {1, n};
res2 = shuffle(qry2);
for(auto &v : res2){
p2[v[0]] = v[1];
p2[v[1]] = v[0];
}
swap(qry1[0][1], qry1[1][1]);
res3 = shuffle(qry1);
for(auto &v : res3){
p3[v[0]] = v[1];
p3[v[1]] = v[0];
}
swap(qry2[0][1], qry2[1][1]);
res4 = shuffle(qry2);
for(auto &v : res4){
p4[v[0]] = v[1];
p4[v[1]] = v[0];
}
vi ans(n+1);
for(int i=1; i<=n; i++){
if(p1[i] != p3[i] and p2[i] == p4[i]) ans[1] = i;
}
for(int i=1; i<=n; i+=2){
int x = p1[ans[i]];
ans[i+1] = x;
if(i+2 <= n) ans[i+2] = p2[x];
}
ans.erase(ans.begin());
return ans;
}
vector<int> solve2(){
vvi qry1(b), qry2(b);
vvi res1, res2, res3;
vi box1(n+1), box2(n+1), box3(n+1);
for(int i=1; i<=n; i++) qry1[(i-1)/k].push_back(i);
res1 = shuffle(qry1);
for(int i=0; i<b; i++){
for(int x : res1[i]){
box1[x] = i;
}
}
for(int i=2; i<=n; i++) qry2[(i-2)/k].push_back(i);
qry2[b-1].push_back(1);
res2 = shuffle(qry2);
for(int i=0; i<b; i++){
for(int x : res2[i]){
box2[x] = i;
}
}
for(int i=1; i<k; i++) swap(qry1[0][i], qry1[1][i-1]);
res3 = shuffle(qry1);
for(int i=0; i<b; i++){
for(int x : res3[i]){
box3[x] = i;
}
}
vi ans(n+1);
for(int i=1; i<=n; i++){
int tf = 1;
for(int j : res1[box1[i]]){
if(i != j and (box2[i] == box2[j] or box3[i] == box3[j])) tf = 0;
}
if(tf) ans[1] = i;
}
for(int i=1; i+k<=n; i+=k){
int bi = box1[ans[i]], box;
for(int j=1; j<=n; j++){
if(j != ans[i] and bi == box1[j]){
box = box2[j];
break;
}
}
for(int j : res2[box]){
if(bi == box1[j]) continue;
ans[i+k] = j;
}
}
vvi c(n+1), r(n+1);
while(c[1] == c[2]){
for(int i=1; i<=n; i++) c[i].push_back((i-1) % b);
sort(c.begin()+1, c.end());
}
int l = c[1].size();
for(int i=1; i<=n; i++){
vi tmp = c[i];
sort(tmp.begin(), tmp.end());
int x = tmp[0];
if(x == tmp[l-1]) swap(c[i], c[x*k+1]);
}
for(int i=0; i<l; i++){
vvi qry(b);
for(int j=1; j<=n; j++) qry[c[j][i]].push_back(j);
vvi res = shuffle(qry);
for(int j=0; j<b; j++){
int v;
for(int x : res[j]){
for(int u=1; u<=n; u+=k){
if(x == ans[u]){
v = u;
break;
}
}
}
for(int x : res[j]) r[x].push_back(c[v][i]);
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(c[i] == r[j]) ans[i] = j;
}
}
ans.erase(ans.begin());
return ans;
}
vector<int> solve(int N, int B, int K, int Q, int ST){
n = N;
b = B;
k = K;
if(k == 2) return solve1();
else return solve2();
}
