#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define all(x) begin(x),end(x)
int dp[20][20],c=0,pw[100];
pair<int,int> pt[100];
int findbitvalue(int num,int bit)
{
return (num/pw[bit])%3;
}
std::vector<std::vector<int>> devise_strategy(int N)
{
pw[0]=1;
for(int i=1;i<=10;i++)
pw[i]=pw[i-1]*3;
// cout<<0<<" represent bit: "<<13<<" val "<<0<<endl;
// 7 in A
// 6 in B
// 0 in B
for(int b=7;b>0;b--)
{
dp[b][2]=++c;
pt[c]={b,2};
// cout<<c<<" represent "<<b<<' '<<2<<endl;
dp[b][1]=++c; // odd
// cout<<c<<" represent bit: "<<b<<" val "<<1<<endl;
pt[c]={b,1};
// cout<<c<<" represent "<<b<<' '<<1<<endl;
dp[b][0]=++c; // even
// cout<<c<<" represent bit: "<<b<<" val "<<0<<endl;
pt[c]={b,0};
// cout<<c<<" represent "<<b<<' '<<0<<endl;
}
pt[0]={8,0};
// B's 0th bit in base-3 is zero
// A's 0th bit will be greater than 0 thus b is smaller
dp[0][0]=-2; // B smaller
dp[0][2]=-1; // A smaller
dp[0][1]=++c; // B smaller
pt[c]={0,1};
// cout<<c<<" represent "<<0<<' '<<1<<endl;
// cout<<c<<endl;
// return {{}};
vector<vector<int>> s;
for(int i=0;i<=c;i++)
{
s.push_back({});
// if(i==0) // start by checking the bit in a
// {
// s[i].push_back(0);
// int bit=12; // check A
// // number bit from 13 to 1
// for(int result=1;result<=N;result++)
// {
// bool p=(result&(1<<bit)); // checking bit 12
// s[i].push_back(dp[bit][p]);
// // even * 2 == multiple of four
// // cout<<"For "<<i<<' '<<result<<' '<<(check*2)+p<<endl;;
// }
// continue;
// }
int bit=pt[i].first;
int val=pt[i].second;
// this bit as calculated last time
// cout<<"Statergy if "<<i<<" on board "<<bit<<' '<<val<<endl;
int cbit=bit-1;
if(bit%2==1) // now check bit in b
{
// cout<<"Ask Bag B"<<endl;
// checking bag B
s[i].push_back(1);
int oth=val;
for(int result=1;result<=N;result++)
{
int p=findbitvalue(result,bit);
// cout<<" If res = "<<result<<" bit "<<p<<endl;
if(oth>p) // bit smaller than the other
{
// cout<<-2<<' ';
s[i].push_back(-2); // B smaller
}
else if(oth<p) // greater than the other
{
// cout<<-1<<' ';
s[i].push_back(-1); // A smaller
}
else
{
p=findbitvalue(result,cbit);
// cout<<"cbit val "<<p<<" transition "<<dp[cbit][p]<<endl;
s[i].push_back(dp[cbit][p]);
}
}
}
else// now check bit in a
{
// cout<<"Ask Bag A"<<endl;
s[i].push_back(0);
int oth=val;
for(int result=1;result<=N;result++)
{
int p=findbitvalue(result,bit);
if(oth>p)
{
// cout<<-1<<' ';
s[i].push_back(-1);
}
else if(oth<p)
{
// cout<<-2<<' ';
s[i].push_back(-2);
}
else if(cbit>=0)
{
p=findbitvalue(result,cbit);
// cout<<dp[cbit][p]<<' ';
s[i].push_back(dp[cbit][p]);
}
else
{
s[i].push_back(-1);
}
}
// cout<<endl;
}
}
return s;
}
