#include "shuffle.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
void flatten(vector<vector<int>> &ans){
for (vector<int> &v: ans){
sort(v.begin(), v.end());
}
}
bool cmp(const vector<int> &a, const vector<int> &b){
return (a[0] == b[0]) && (a[1] == b[1]);
}
vector<int> intersection(vector<int> &a, vector<int> &b){
vector<int> ret;
for (int &adef: a){
for (int &a1: b){
if (a1 == adef){
ret.push_back(a1);
}
}
}
return ret;
}
vector<int> sub4(int n){
// k == 2
/*
(1, 2), (3, 4), (5, 6), ...., (n-1, n)
(1, 3), (2, 4), (5, 6), ...., (n-1, n)
(1, 5), (3, 4), (2, 6), ...., (n-1, n)
(1, 3), (4, 5), (6, 7), ...., (n, 2)
*/
vector<vector<int>> askArr(n/2, vector<int>()), ans1, ans2, ans3, ans4;
for (int i = 0; i < n/2; i++){
askArr[i].push_back(i*2 + 1);
askArr[i].push_back(i*2 + 2);
}
ans1 = shuffle(askArr);
flatten(ans1);
askArr.assign(n/2, vector<int>());
askArr[0] = {1, 3};
askArr[1] = {2, 4};
askArr[2] = {5, 6};
for (int i = 3; i < n/2; i++){
askArr[i].push_back(i*2 + 1);
askArr[i].push_back(i*2 + 2);
}
ans2 = shuffle(askArr);
flatten(ans2);
askArr.assign(n/2, vector<int>());
askArr[0] = {1, 5};
askArr[1] = {3, 4};
askArr[2] = {2, 6};
for (int i = 3; i < n/2; i++){
askArr[i].push_back(i*2 + 1);
askArr[i].push_back(i*2 + 2);
}
ans3 = shuffle(askArr);
flatten(ans3);
askArr.assign(n/2, vector<int>());
askArr[0] = {1, 3};
askArr[n/2-1] = {n, 2};
for (int i = 1; i < n/2-1; i++){
askArr[i].push_back(i*2 + 2);
askArr[i].push_back(i*2 + 3);
}
ans4 = shuffle(askArr);
flatten(ans4);
// find common query of 2, 4 -> (1, 3)
// find common query of 1, 3 not in 2 -> (3, 4)
// find 3 -> find 1, find everything else
vector<int> oneThree, threeFour, ans(n);
bool found1 = false;
for (vector<int> &v1: ans2){
for (vector<int> &v2: ans4){
if (cmp(v1, v2)){
oneThree = v1;
found1 = true;
break;
}
}
if (found1){
break;
}
}
vector<vector<int>> cand;
for (vector<int> &v1: ans1){
for (vector<int> &v2: ans3){
if (cmp(v1, v2)){
cand.push_back(v1);
}
}
}
for (vector<int> &v: cand){
bool can = true;
for (vector<int> &vNot: ans2){
if (cmp(v, vNot)){
can = false;
break;
}
}
if (can){
threeFour = v;
break;
}
}
// find common element in oneThree and threeFour
map<int, int> tot;
tot[oneThree[0]]++;
tot[oneThree[1]]++;
tot[threeFour[0]]++;
tot[threeFour[1]]++;
// cout << oneThree[0] << ' ' << oneThree[1] << endl;
// cout << threeFour[0] << ' ' << threeFour[1] << endl;
for (auto &pa: tot){
if (pa.second == 2){
ans[2] = pa.first;
break;
}
}
if (ans[2] == oneThree[0]){
ans[0] = oneThree[1];
}
else ans[0] = oneThree[0];
// scale
for (int i = 2; i <= n; i++){
if (i == 3){
continue;
}
if (i % 2 == 0){
for (vector<int> &v: ans1){
if (v[0] == ans[i-2] || v[1] == ans[i-2]){
if (v[0] == ans[i-2]){
ans[i-1] = v[1];
}
else ans[i-1] = v[0];
}
}
}
else{
for (vector<int> &v: ans4){
if (v[0] == ans[i-2] || v[1] == ans[i-2]){
if (v[0] == ans[i-2]){
ans[i-1] = v[1];
}
else ans[i-1] = v[0];
}
}
}
}
// for (int i = 0; i < n; i++){
// cout << ans[i] << ' ';
// }
// cout << endl;
return ans;
}
// log sub 6
// small B first
// find head of each box => turn in to sub3 => b + log(b)
// now do small k
vector<int> sub6(int n, int b, int k){
// query (1, 2, 3, ..., k), ... (..., n-1, n)
// query (n, 2, 3, ..., k), ... (..., n-1, 1)
// query (n-1, 2, 3, ..., k), ... (..., 1, n)
// find diff elements, get (1, n) pair and (1, n-1 pair)
// get 1, n, n-1
vector<int> ans(n), head(b);
vector<vector<int>> askQuery(b, vector<int>(k, 0)), ret1;
int cnt = 1;
for (int bi = 0; bi < b; bi++){
for(int i = 0; i < k; i++){
askQuery[bi][i] = cnt++;
}
}
ret1 = shuffle(askQuery);
flatten(ret1);
vector<vector<int>> ret2, ret3;
swap(askQuery[0][0], askQuery[1][0]);
ret2 = shuffle(askQuery);
flatten(ret2);
swap(askQuery[0][0], askQuery[1][0]);
swap(askQuery[0][0], askQuery[2][0]);
ret3 = shuffle(askQuery);
flatten(ret3);
swap(askQuery[0][0], askQuery[2][0]);
vector<int> oneCand;
for (vector<int> &vdef: ret1){
for (vector<int> &v1: ret2){
int match = 0, elem = 0;
for (int &adef: vdef){
for (int &a1: v1){
if (a1 == adef){
match++;
elem = a1;
}
}
}
if (match == 1){
oneCand.push_back(elem);
}
}
}
for (vector<int> &vdef: ret1){
for (vector<int> &v1: ret3){
int match = 0, elem = 0;
for (int &adef: vdef){
for (int &a1: v1){
if (a1 == adef){
match++;
elem = a1;
}
}
}
if (match == 1){
oneCand.push_back(elem);
}
}
}
map<int, int> mp;
for (int &ai: oneCand){
mp[ai]++;
}
for (auto &pa: mp){
if (pa.se == 2){
head[0] = pa.fi;
break;
}
}
if (head[0] == oneCand[0]){
head[1] = oneCand[1];
}
else head[1] = oneCand[0];
if (head[0] == oneCand[2]){
head[2] = oneCand[3];
}
else head[2] = oneCand[2];
// cout << head[0] << ' ' << head[1] << ' ' << head[2] << endl;
vector<vector<vector<int>>> ansSeg(b, vector<vector<int>>(1, vector<int>()));
vector<pair<pair<int, int>, pair<int, int>>> segs(1);
for (int bi = 0; bi < b; bi++){
segs[0] = {{0, 0}, {0, k-1}};
}
// prevRet is ordered, ordering takes place upon next query asked
int queryNum = 0;
vector<vector<int>> firstSegments(b, vector<int>()), prevBox(b, vector<int>());
while(true){
// cout << "query " << queryNum << ": --------------------------------------" << endl;
int conditionToBreak = true;
// decompose each part into half, then cyclic shift
int len = segs.size();
for (int i = 0; i < len; i++){
int shift = segs[i].fi.fi;
int seg = segs[i].fi.se;
int l = segs[i].se.fi, r = segs[i].se.se;
if (l == r){
continue;
}
else{
conditionToBreak = false;
}
// case 1: l + 1 = r
if (l + 1 == r){
int mid = (l + r)/2;
segs[i].se = {l, mid};
segs.push_back({{1, i}, {mid+1, r}});
for (int bi = 0; bi < b; bi++){
ansSeg[bi].push_back(vector<int>());
}
// cyclic shift the second seg on askQuery
vector<int> tmp = askQuery[0], tmp2;
for (int i = mid+1; i <= r; i++){
askQuery[0][i] = askQuery[b-1][i];
}
for (int i = 0; i < b-1; i++){
// paste it in
tmp2 = askQuery[i+1];
for (int j = mid+1; j <= r; j++){
askQuery[i+1][j] = tmp[j];
}
tmp = tmp2;
}
}
else{
// case 2: split by 3
int len = (r - l + 1)/3;
int mid1 = l + len - 1;
int mid2 = l + 2*len - 1;
segs[i].se = {l, mid1};
segs.push_back({{1, i}, {mid1+1, mid2}});
segs.push_back({{2, i}, {mid2+1, r}});
for (int bi = 0; bi < b; bi++){
ansSeg[bi].push_back(vector<int>());
ansSeg[bi].push_back(vector<int>());
}
// cyclic shift the second seg on askQuery
vector<int> tmp = askQuery[0], tmp2;
for (int i = mid1 + 1; i <= mid2; i++){
askQuery[0][i] = askQuery[b-1][i];
}
for (int i = 0; i < b-1; i++){
// paste it in
tmp2 = askQuery[i+1];
for (int j = mid1+1; j <= mid2; j++){
askQuery[i+1][j] = tmp[j];
}
tmp = tmp2;
}
// cyclic shift by 2
vector<int> tmp3;
tmp = askQuery[0];
tmp2 = askQuery[1];
for (int i = mid2+1; i <= r; i++){
askQuery[0][i] = askQuery[b-2][i];
askQuery[1][i] = askQuery[b-1][i];
}
for (int i = 0; i < b-2; i++){
// paste it in
tmp3 = askQuery[i+2];
for (int j = mid2+1; j <= r; j++){
askQuery[i+2][j] = tmp[j];
}
tmp = tmp2;
tmp2 = tmp3;
}
}
}
// cannot decompose anymore, keep current answer
if (conditionToBreak){
// just before break, save some ans
break;
}
// cout << "query and ans\n";
// for (int bi = 0; bi < b; bi++){
// for (int i = 0; i < k; i++){
// cout << askQuery[bi][i] << ' ';
// }
// cout << endl;
// }
// cout << endl;
vector<vector<int>> retMid = shuffle(askQuery), boxAns(b);
// for (int bi = 0; bi < b; bi++){
// for (int i = 0; i < k; i++){
// cout << retMid[bi][i] << ' ';
// }
// cout << endl;
// }
// cout << endl;
// know: head 0, 1, 2
// now that we have extra information from the 2nd query
// identify box 0, 1, 2
// for i, consider box i-1, i-2, i-3
// box i would consist of (i-1, i-2) and not i-3, this box is unique
// let box i = that box
// we can sort the boxes in the 1st query
// thus, firstSegments of box bi -> the entire array
if (queryNum == 0){
for (int bi = 0; bi <= 2; bi++){
int found = false;
vector<int> setAns;
for (vector<int> v: ret1){
for (int &aDef: v){
if (aDef == head[bi]){
found = 1;
setAns = v;
break;
}
}
if (found){
break;
}
}
ansSeg[bi][0] = setAns;
prevBox[bi] = setAns;
firstSegments[bi] = setAns;
}
for (int bi = 3; bi < b; bi++){
for (vector<int> v: retMid){
vector<int> seg0 = intersection(v, prevBox[bi-1]);
vector<int> seg1 = intersection(v, prevBox[bi-2]);
vector<int> seg2 = intersection(v, prevBox[bi-3]);
if (seg2.size() == 0 && seg0.size() > 0 && seg1.size() > 0){
// take the unknown part then search for it in original array
vector<int> unknown;
for (int ai: v){
bool ignored = false;
for (int ignore: seg0){
if (ai == ignore){
ignored = true;
break;
}
}
for (int ignore: seg1){
if (ai == ignore){
ignored = true;
break;
}
}
if (!ignored) unknown.push_back(ai);
}
for (vector<int> vDef: ret1){
if (intersection(unknown, vDef).size() > 0){
ansSeg[bi][0] = vDef;
prevBox[bi] = vDef;
firstSegments[bi] = vDef;
break;
}
}
break;
}
}
}
}
// given the previous box in order,
// find boxes 0, 1, 2, then take intersection with last query to get firstSegments
// cout << "prev firstSegment:" << endl;
// for(int bi = 0; bi < b; bi++){
// for (int ai: firstSegments[bi]){
// cout << ai << ' ';
// }
// cout << endl;
// }
// cout << endl;
vector<vector<int>> newFirstSegments(b);
for (int bi = 0; bi <= 2; bi++){
int found = false;
vector<int> setAns;
for (vector<int> v: retMid){
for (int &aDef: v){
if (aDef == head[bi]){
found = 1;
setAns = v;
break;
}
}
if (found){
break;
}
}
// setAns is the box
boxAns[bi] = setAns;
newFirstSegments[bi] = intersection(setAns, firstSegments[bi]);
}
for (int bi = b-1; bi > 2; bi--){
int idx1 = (bi + 2 + b)%b;
int idx2 = (bi + 1 + b)%b;
if (firstSegments[bi].size() == 1){
newFirstSegments[bi] = firstSegments[bi];
}
else{
for (int ai: firstSegments[bi]){
auto it1 = find(boxAns[idx1].begin(), boxAns[idx1].end(), ai);
auto it2 = find(boxAns[idx2].begin(), boxAns[idx2].end(), ai);
if (it1 == boxAns[idx1].end() && it2 == boxAns[idx2].end()){
newFirstSegments[bi].push_back(ai);
}
}
}
for (vector<int> vFind: retMid){
if (intersection(newFirstSegments[bi], vFind).size() > 0){
boxAns[bi] = vFind;
break;
}
}
}
firstSegments = newFirstSegments;
// cout << "aft firstSegment:" << endl;
// for(int bi = 0; bi < b; bi++){
// for (int ai: firstSegments[bi]){
// cout << ai << ' ';
// }
// cout << endl;
// }
// cout << endl;
// cout << "boxes: \n";
// for (int bi = 0; bi < b; bi++){
// for (int i = 0; i < k; i++){
// cout << boxAns[bi][i] << ' ';
// }
// cout << endl;
// }
// cout << endl;
// now that order of box is sorted, we will rebuild ansSeg
vector<vector<vector<int>>> newAnsSeg(b, vector<vector<int>>(segs.size(), vector<int>()));
for (int i = 0; i < segs.size(); i++){
int shift = segs[i].fi.fi;
int seg = segs[i].fi.se;
for (int bi = 0; bi < b; bi++){
// shift =
int oldSeg = seg;
int oldBox = (bi-shift+b)%b;
for (int aOld: ansSeg[oldBox][oldSeg]){
for (int aAns: boxAns[bi]){
if (aOld == aAns){
newAnsSeg[bi][i].push_back(aOld);
}
}
}
}
}
ansSeg = newAnsSeg;
// for (int i = 0; i < segs.size(); i++){
// cout << "segments: " << i << endl;
// for (int bi = 0; bi < b; bi++){
// cout << "box " << bi << ": " << endl;
// for (int &a: ansSeg[bi][i]){
// cout << a << ' ';
// }
// cout << endl;
// }
// cout << endl;
// }
// cout << endl;
// reset all shifts, as each one is stored in the correct ansSegs
for (int i = 0; i < segs.size(); i++){
segs[i].fi = {0, i};
}
prevBox = boxAns;
queryNum++;
}
// build ans from askQuery, ansSeg and segs
int len = segs.size();
for (int i = 0; i < len; i++){
// all segs are 1 len
int l = segs[i].se.fi;
for (int bi = 0; bi < b; bi++){
if (askQuery[bi][l]-1 % k == 0) continue;
ans[askQuery[bi][l]-1] = ansSeg[bi][i][0];
}
}
for (int bi = 0; bi < b; bi++){
ans[bi*k] = firstSegments[bi][0];
}
// for (int i = 0; i < n; i++){
// cout << ans[i] << ' ';
// }
return ans;
}
// sub 5
// query (b1, b2), swap query 1, n/2+1, 1, n
// find 1
// then do dnc
vector<int> sub5(int n, int b, int k){
// query (1, 2, 3, ..., k), ... (..., n-1, n)
// query (n, 2, 3, ..., k), ... (..., n-1, 1)
// query (n-1, 2, 3, ..., k), ... (..., 1, n)
// find diff elements, get (1, n) pair and (1, n-1 pair)
// get 1, n, n-1
vector<int> ans(n);
vector<vector<int>> askQuery(b, vector<int>(k, 0)), ret1, ret2, ret3;
int cnt = 1;
for (int bi = 0; bi < b; bi++){
for(int i = 0; i < k; i++){
askQuery[bi][i] = cnt++;
}
}
ret1 = shuffle(askQuery);
flatten(ret1);
swap(askQuery[0][0], askQuery[b-1][k-1]);
ret2 = shuffle(askQuery);
flatten(ret2);
swap(askQuery[0][0], askQuery[b-1][k-1]);
swap(askQuery[0][0], askQuery[b-1][k-2]);
ret3 = shuffle(askQuery);
flatten(ret3);
swap(askQuery[0][0], askQuery[b-1][k-2]);
vector<int> oneCand;
for (vector<int> &vdef: ret1){
for (vector<int> &v1: ret2){
int match = 0, elem = 0;
for (int &adef: vdef){
for (int &a1: v1){
if (a1 == adef){
match++;
elem = a1;
}
}
}
if (match == 1){
oneCand.push_back(elem);
}
}
}
for (vector<int> &vdef: ret1){
for (vector<int> &v1: ret3){
int match = 0, elem = 0;
for (int &adef: vdef){
for (int &a1: v1){
if (a1 == adef){
match++;
elem = a1;
}
}
}
if (match == 1){
oneCand.push_back(elem);
}
}
}
// oneCand now has 4 entry, most common entry is 1
map<int, int> mp;
for (int &ai: oneCand){
mp[ai]++;
}
for (auto &pa: mp){
if (pa.se == 2){
ans[0] = pa.fi;
break;
}
}
if (ans[0] == oneCand[0]){
ans[n-1] = oneCand[1];
}
else ans[n-1] = oneCand[0];
if (ans[0] == oneCand[2]){
ans[n-2] = oneCand[3];
}
else ans[n-2] = oneCand[2];
// cout << ans[0] << ' ' << ans[n-1] << ' ' << ans[n-2] << endl;
// found 1, n
// do segment dnc, segs[bi] = elements of segs[bi] in askQuery
// ansSeg[bi] = possible number sets in segs[bi]
// segs -> all segments in a box
// stop dividing when r == l
int head = ans[0];
vector<vector<vector<int>>> ansSeg(b, vector<vector<int>>(1, vector<int>()));
vector<pair<int, pair<int, int>>> segs(1);
for (int bi = 0; bi < b; bi++){
segs[0] = {-1, {0, k-1}};
}
int has = false;
for (int &ai: ret1[0]){
if (ai == head){
has = true;
break;
}
}
if (has){
ansSeg[0][0] = ret1[0];
ansSeg[1][0] = ret1[1];
}
else{
ansSeg[0][0] = ret1[1];
ansSeg[1][0] = ret1[0];
}
while(true){
int conditionToBreak = true;
// decompose each part into half, then cyclic shift
int len = segs.size();
for (int i = 0; i < len; i++){
int shift = segs[i].fi;
int l = segs[i].se.fi, r = segs[i].se.se;
if (l == r){
continue;
}
else{
conditionToBreak = false;
}
int mid = (l + r)/2;
segs[i].se = {l, mid};
segs.push_back({i, {mid+1, r}});
for (int bi = 0; bi < b; bi++){
ansSeg[bi].push_back(vector<int>());
}
// cyclic shift the second seg on askQuery
vector<int> tmp = askQuery[0], tmp2;
for (int i = mid+1; i <= r; i++){
askQuery[0][i] = askQuery[b-1][i];
}
for (int i = 0; i < b-1; i++){
// paste it in
tmp2 = askQuery[i+1];
for (int j = mid+1; j <= r; j++){
askQuery[i+1][j] = tmp[j];
}
tmp = tmp2;
}
}
// cannot decompose anymore, keep current answer
if (conditionToBreak){
break;
}
// for (int bi = 0; bi < b; bi++){
// for (int i = 0; i < k; i++){
// cout << askQuery[bi][i] << ' ';
// }
// cout << endl;
// }
vector<vector<int>> retMid = shuffle(askQuery), boxAns(b);
// rebuild ansSeg
int hasHead = false;
for (int &ai: retMid[0]){
if (ai == head){
hasHead = true;
break;
}
}
if (hasHead){
boxAns[0] = retMid[0];
boxAns[1] = retMid[1];
}
else{
boxAns[0] = retMid[1];
boxAns[1] = retMid[0];
}
// for (int bi = 0; bi < b; bi++){
// for (int i = 0; i < k; i++){
// cout << boxAns[bi][i] << ' ';
// }
// cout << endl;
// }
// cout << endl;
// now that order of box is sorted, we will rebuild ansSeg
vector<vector<vector<int>>> newAnsSeg(b, vector<vector<int>>(segs.size(), vector<int>()));
for (int i = 0; i < segs.size(); i++){
int shift = segs[i].fi;
for (int bi = 0; bi < b; bi++){
// shift =
int oldSeg = (shift == -1 ? i : shift);
int oldBox = (shift == -1 ? bi : (bi-1+b)%b);
for (int aOld: ansSeg[oldBox][oldSeg]){
for (int aAns: boxAns[bi]){
if (aOld == aAns){
newAnsSeg[bi][i].push_back(aOld);
}
}
}
}
}
ansSeg = newAnsSeg;
// for (int i = 0; i < segs.size(); i++){
// cout << "segments: " << i << endl;
// for (int bi = 0; bi < b; bi++){
// cout << "box " << bi << ": " << endl;
// for (int &a: ansSeg[bi][i]){
// cout << a << ' ';
// }
// cout << endl;
// }
// cout << endl;
// }
// cout << endl;
// reset all shifts, as each one is stored in the correct ansSegs
for (int i = 0; i < segs.size(); i++){
segs[i].fi = -1;
}
}
// build ans from askQuery, ansSeg and segs
int len = segs.size();
for (int i = 0; i < len; i++){
// all segs are 1 len
int l = segs[i].se.fi;
for (int bi = 0; bi < b; bi++){
ans[askQuery[bi][l]-1] = ansSeg[bi][i][0];
}
}
// for (int i = 0; i < n; i++){
// cout << ans[i] << ' ';
// }
// cout << endl;
return ans;
}
// sub3
// same thing as sub5 but no need to find first ans
vector<int> sub3(int n, int b, int k){
vector<int> ans(n);
vector<vector<int>> askQuery(b, vector<int>(k, 0)), ret1, ret2, ret3;
int cnt = 1;
for (int bi = 0; bi < b; bi++){
for(int i = 0; i < k; i++){
askQuery[bi][i] = cnt++;
}
}
ret1 = shuffle(askQuery);
flatten(ret1);
vector<vector<vector<int>>> ansSeg(b, vector<vector<int>>(1, vector<int>()));
vector<pair<int, pair<int, int>>> segs(1);
for (int bi = 0; bi < b; bi++){
segs[0] = {-1, {0, k-1}};
}
for (int bi = 0; bi < b; bi++){
ansSeg[bi][0] = ret1[bi];
}
while(true){
int conditionToBreak = true;
// decompose each part into half, then cyclic shift
int len = segs.size();
for (int i = 0; i < len; i++){
int shift = segs[i].fi;
int l = segs[i].se.fi, r = segs[i].se.se;
if (l == r){
continue;
}
else{
conditionToBreak = false;
}
int mid = (l + r)/2;
segs[i].se = {l, mid};
segs.push_back({i, {mid+1, r}});
for (int bi = 0; bi < b; bi++){
ansSeg[bi].push_back(vector<int>());
}
// cyclic shift the second seg on askQuery
vector<int> tmp = askQuery[0], tmp2;
for (int i = mid+1; i <= r; i++){
askQuery[0][i] = askQuery[b-1][i];
}
for (int i = 0; i < b-1; i++){
// paste it in
tmp2 = askQuery[i+1];
for (int j = mid+1; j <= r; j++){
askQuery[i+1][j] = tmp[j];
}
tmp = tmp2;
}
}
// cannot decompose anymore, keep current answer
if (conditionToBreak){
break;
}
// for (int bi = 0; bi < b; bi++){
// for (int i = 0; i < k; i++){
// cout << askQuery[bi][i] << ' ';
// }
// cout << endl;
// }
vector<vector<int>> boxAns = shuffle(askQuery);
// rebuild ansSeg
// for (int bi = 0; bi < b; bi++){
// for (int i = 0; i < k; i++){
// cout << boxAns[bi][i] << ' ';
// }
// cout << endl;
// }
// cout << endl;
// now that order of box is sorted, we will rebuild ansSeg
vector<vector<vector<int>>> newAnsSeg(b, vector<vector<int>>(segs.size(), vector<int>()));
for (int i = 0; i < segs.size(); i++){
int shift = segs[i].fi;
for (int bi = 0; bi < b; bi++){
// shift =
int oldSeg = (shift == -1 ? i : shift);
int oldBox = (shift == -1 ? bi : (bi-1+b)%b);
for (int aOld: ansSeg[oldBox][oldSeg]){
for (int aAns: boxAns[bi]){
if (aOld == aAns){
newAnsSeg[bi][i].push_back(aOld);
}
}
}
}
}
ansSeg = newAnsSeg;
// for (int i = 0; i < segs.size(); i++){
// cout << "segments: " << i << endl;
// for (int bi = 0; bi < b; bi++){
// cout << "box " << bi << ": " << endl;
// for (int &a: ansSeg[bi][i]){
// cout << a << ' ';
// }
// cout << endl;
// }
// cout << endl;
// }
// cout << endl;
// reset all shifts, as each one is stored in the correct ansSegs
for (int i = 0; i < segs.size(); i++){
segs[i].fi = -1;
}
}
// build ans from askQuery, ansSeg and segs
int len = segs.size();
for (int i = 0; i < len; i++){
// all segs are 1 len
int l = segs[i].se.fi;
for (int bi = 0; bi < b; bi++){
ans[askQuery[bi][l]-1] = ansSeg[bi][i][0];
}
}
// for (int i = 0; i < n; i++){
// cout << ans[i] << ' ';
// }
// cout << endl;
return ans;
}
vector<int> solve(int N, int B, int K, int Q, int ST) {
if (ST == 2 || ST == 4){
return sub4(N);
}
else if (ST == 3){
return sub3(N, B, K);
}
else if (ST == 1 || ST == 5){
return sub5(N, B, K);
}
return sub6(N, B, K);
}
