#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;
map<ii, int> M;
bool query(int a, int b){
if(M.find(ii(a,b)) != M.end()) return M[ii(a,b)];
int res = Query(a,b);
//show3(a,b,res);
M[ii(a,b)] = res;
M[ii(b,a)] = not res;
return res;
}
struct thing{
int s, e, c;
};
vector<int> Solve(int n) {
vector<int> T(0);
vector<int> A(n);
vector<int> B(n);
//for (int i = 0; i < n; i++) T[i] = i;
for (int i = 0; i < n; i++) A[i] = 0;
for (int i = 0; i < n; i++) B[i] = 0;
int seed = time(0);
//srand(1622964658);
srand(1622968914);
T.push_back(0);
for(int i = 1;i < n;i++){
int low = -1, high = sz(T);
while(low != high-1){
int mid = (low+high)/2;
if(query(T[mid], i)) high = mid;
else low = mid;
}
T.insert(T.begin()+low+1, i);
}
//cerr << "------------" << endl;
//cerr << "------------" << endl;
int a = 0;
bool awins = false;
vector<thing> ranges;
for(int i = 1;i < n;i++){
if(i <= a+1) continue;
//show2(a,i)
if(i == a+2) awins = query(T[a], T[i]);
else{
if(awins){
if(not query(T[a], T[i])){
if(i-1 == a+2){
ranges.push_back({a,i-1,2});
}
else{
ranges.push_back({a,i-1,1});
}
a = i;
}
}
else{
if(query(T[a], T[i])){
ranges.push_back({a,i,2});
a = i+1;
}
}
}
}
if(a != n) ranges.push_back({a,n-1,1});
int zero = -1;
if(ranges[0].e != 2){
///solve range 0;
int e = ranges[0].e;
int x = e;
int cnt = 0;
int e2 = ranges[0].e;
if(sz(ranges) > 1) e2 = ranges[1].e;
for(int i = 0;i <= e2;i++){
if(i == x) continue;
if(query(T[x], T[i])) cnt++;
}
if(ranges[0].c == 2){
if(cnt == 1) zero = 0;
else zero = 1;
}
else{
if(cnt == 1) zero = e;
else zero = e-1;
}
}
else{
int x = 0;
while(x < 2){
int cnt = 0;
int e2 = ranges[0].e;
if(sz(ranges) > 1) e2 = ranges[1].e;
for(int i = 0;i <= e2;i++){
if(i == x) continue;
if(query(T[x], T[i])) cnt++;
}
if(cnt != 1){
break;
}
x++;
}
zero = (x+2)%3;
}
//show(zero);
for(int i = 0;i <= ranges[0].e;i++){
A[i] = T[(zero-i+ranges[0].e+1)%(ranges[0].e+1)];
}
for(int rno = 1;rno < sz(ranges);rno++){
int s = ranges[rno].s; int e = ranges[rno].e;
int z = s;
int L = (e-s+1);
for(int i = 0;i < L;i++){
if(query(A[s-1],T[i+s])){
z = i+s;
break;
}
if(query(A[s-1],T[e-i])){
z = e-i;
break;
}
}
//show(z);
for(int i = 0;i < L;i++){
A[i+s] = T[(z-i-s+L+L)%L+s];
}
}
for(int i = 0;i < n;i++) B[A[i]] = i;
//cerr << "------------" << endl;
return B;
}
