#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1005;
int b, k, n, one, Nr;
vector<vector<int>> query[15], ans1, ans2, ans3, to0, W[15];
vector<int> cycle;
int marked[Nmax][Nmax], on_cycle[Nmax];
int marked1[Nmax], marked2[Nmax], val[Nmax];
void step1()
{
vector<int> aux;
vector<vector<int>> to1, to2;
int i, j;
for(i=1; i<=b; ++i)
{
aux.clear();
for(j=i*k-k+1; j<=i*k; ++j)
aux.push_back(j);
to1.push_back(aux);
}
ans1 = query[1] = shuffle(to1);
for(i=1; i<b; ++i)
{
aux.clear();
for(j=i*k-k+2; j<=i*k+1; ++j)
aux.push_back(j);
to2.push_back(aux);
}
aux.clear();
aux.push_back(1);
for(i=n-k+2; i<=n; ++i) aux.push_back(i);
to2.push_back(aux);
ans2 = shuffle(to2);
aux.clear();
aux.push_back(1);
for(i=k+2; i<=2*k; ++i) aux.push_back(i);
to0 = to1;
to1[0] = aux;
to1[1] = to2[0];
ans3 = shuffle(to1);
for(auto it : ans1)
for(auto x : it)
for(auto y : it)
marked[x][y] ++, marked1[x] = max(marked1[x], x!=y ? y : 0);
for(auto it : ans2)
for(auto x : it)
for(auto y : it)
marked[x][y] ++, marked2[x] = max(marked2[x], x!=y ? y : 0);
for(i=1; i<=n; ++i)
{
bool ok = 1;
for(j=1; ok && j<=n; ++j)
if(i != j && marked[i][j] > 1)
ok = 0;
if(ok) on_cycle[i] = 1;
}
for(auto it : ans3)
for(auto x : it)
for(auto y : it)
marked[x][y] ++;
for(i=1; i<=n; ++i)
{
bool ok = 1;
for(j=1; ok && j<=n; ++j)
if(i != j && marked[i][j] > 1)
ok = 0;
if(ok) one = i;
}
cycle.push_back(one);
while(cycle.size() < b)
{
for(i=1; i<=n; ++i)
if(on_cycle[i] && marked1[cycle.back()] == marked2[i])
{
cycle.push_back(i);
break;
}
}
for(i=0; i<b; ++i) val[cycle[i]] = i * k + 1;
}
void divide(vector<vector<int>> &to)
{
bool ok = 0;
int i, j;
for(auto it : to)
if(it.size() > 1) ok = 1;
if(!ok) return;
vector<vector<int>> w;
for(auto it : to)
{
int cat, rest;
cat = it.size() / b;
rest = it.size() % b;
int id = 0;
for(i=0; i<b; ++i)
{
vector<int> aux;
for(j=0; j<cat; ++j)
aux.push_back(it[id++]);
if(i < rest) aux.push_back(it[id++]);
w.push_back(aux);
}
}
vector<vector<int>> q;
for(i=0; i<b; ++i)
{
int rest;
int C = w.size() / b, id;
vector<int> aux;
for(j=0, rest = i; j<b; ++j, rest = (rest+1) % b)
{
for(id = C * j + rest; id < C * (j+1); id += b)
for(auto it : w[id])
aux.push_back(it);
}
q.push_back(aux);
}
W[++Nr] = q;
query[++Nr] = shuffle(q);
divide(w);
}
vector<int> solve6()
{
W[Nr = 1] = to0;
divide(to0);
vector<int> where(1e6 + 5, -1);
vector<int> who(n+1, 0), whoo(n+1, 0);
int i;
for(i=1; i<=Nr; ++i)
for(auto it : query[i])
{
int rep;
for(auto x : it)
if(on_cycle[x]) rep = val[x] / k;
for(auto x : it)
who[x] = who[x] * b + rep;
}
for(i=1; i<=n; ++i)
where[who[i]] = i;
for(auto itt : W)
for(auto it : itt)
{
int rep;
for(auto x : it)
if(x % k == 1) rep = x / k;
for(auto x : it)
whoo[x] = whoo[x] * b + rep;
}
vector<int> p(n);
for(i=1; i<=n; ++i)
p[i-1] = where[whoo[i]];
return p;
}
vector<int> solve(int N, int B, int K, int Q, int ST)
{
n = B * K;
b = B;
k = K;
if(ST != 6) return vector<int> ();
step1();
return solve6();
}
