#include "monster.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
map<pair<int,int>,int>mp;
bool query(int a, int b) {
if(mp.find({a, b})!=mp.end()) return mp[{a, b}];
if(Query(a, b)) {
mp[{a, b}]=1;
mp[{b, a}]=0;
} else {
mp[{b, a}]=1;
mp[{a, b}]=0;
}
return mp[{a, b}];
}
vector<int>cd(vector<int>T) {
if(T.size()==1) return T;
vector<int>A, B;
rep(i, T.size()/2) A.pb(T[i]);
for(int i=T.size()/2; i<T.size(); ++i) B.pb(T[i]);
A=cd(A);
B=cd(B);
int l1=0, l2=0;
vector<int>P;
while(l1<A.size() && l2<B.size()) {
if(query(A[l1], B[l2])==false) P.pb(A[l1++]);
else P.pb(B[l2++]);
}
while(l1<A.size()) P.pb(A[l1++]);
while(l2<B.size()) P.pb(B[l2++]);
return P;
}
vector<int>Solve(int n) {
vector<int>T(n);
rep(i, n) T[i]=i;
T=cd(T);
string s="";
if(query(T[0], T[2])) s+="1"; else s+="0";
if(query(T[0], T[3])) s+="1"; else s+="0";
if(query(T[1], T[3])) s+="1"; else s+="0";
int l=0;
if(s=="001" || s=="011" || s=="101") {
l=1;
} else if(s=="000" || s=="010") {
reverse(T.begin(), T.begin()+2);
l=2;
} else if(s=="110") {
reverse(T.begin(), T.begin()+3);
l=3;
} else if(s=="111") {
l=4;
while(l<n) {
if(query(T[l-2], T[l])==false) break;
++l;
}
reverse(T.begin(), T.begin()+l);
} else {
l=4;
while(l<n) {
if(query(T[0], T[l])==true) {
swap(T[0], T[2]);
break;
}
if(query(T[1], T[l])==true) {
swap(T[1], T[2]);
break;
}
if(query(T[2], T[l])==true) {
swap(T[0], T[1]);
break;
}
++l;
}
++l;
reverse(T.begin()+3, T.begin()+l);
}
while(l<n) {
int p=l;
while(query(T[l-1], T[p])==false) ++p;
reverse(T.begin()+l, T.begin()+p+1);
l=p+1;
}
vector<int>P(n);
rep(i, n) P[T[i]]=i;
return P;
}
