#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target("sse4")
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
//#define randi uniform_int_distribution<long long>
#define damoon(v) v.resize(unique(all(v))-v.begin())
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//randi dist(0,10000000000000000);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,bool> pib;
typedef pair<long long,bool> plb;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef vector<int> veci;
typedef vector<long long> vecl;
typedef vector<bool> vecb;
typedef vector<pii> vecp;
typedef set<int> seti;
typedef set<long long> setl;
typedef set<pii> setp;
typedef map<int,int> mapii;
typedef map<long long,long long> mapll;
typedef map<int,bool> mapib;
typedef map<long long,bool> maplb;
const int inf=1e9,mod=1e9+7,neginf=-1e9;
constexpr int N=100;
const double PI=acos(-1);
static int gn,gw;
static int tos[N],res[N],ss[N];
inline void ZS(int n)
{
fill(tos,tos+n,0);
}
int minValue(int n,int w)
{
gn=n;
gw=w;
ZS(n);
tos[0]=1;
playRound(tos,res);
for(int i=0;i<n;i++)
if(res[i]==0)
return i;
return 0;
}
int maxValue(int n,int w)
{
gn=n;
gw=w;
veci cans;
cans.reserve(n);
for(int i=0;i<n;i++)
cans.pub(i);
while(cans.size()>1)
{
int cnt=w/(int)cans.size();
if(cnt<=0)
cnt=1;
ZS(n);
for(int ind:cans)
tos[ind]=cnt;
playRound(tos,res);
veci nxt;
nxt.reserve(cans.size());
for(int ind:cans)
if(res[ind]>cnt)
nxt.pub(ind);
if(nxt.empty())
{
int bst=-1;
for(int ind:cans)
bst=max(bst,res[ind]);
for(int ind:cans)
if(res[ind]==bst)
nxt.pub(ind);
}
swap(cans,nxt);
}
return cans.empty()?0:cans[0];
}
int greaterValue(int n,int w)
{
gn=n;
gw=w;
int L=0,R=10;
while(L+1<R)
{
int mid=(L+R)>>1;
int sn=mid;
tos[0]=tos[1]=sn;
playRound(tos,res);
bool al=(res[0]<=sn);
bool bl=(res[1]<=sn);
if(al and bl)
R=mid;
else if(!al and !bl)
L=mid;
else
return (res[0]<res[1]);
}
int sn=R;
tos[0]=sn;
tos[1]=sn;
playRound(tos,res);
return (res[0]<res[1]);
}
bool cmp1(int a,int b)
{
int pr=max(1,gw/2);
ZS(gn);
tos[a]=tos[b]=pr;
playRound(tos,res);
return res[a]<res[b];
}
void C1(int ll,int lr,int rl,int rr)
{
queue<int> a,b,c;
for(int i=ll;i<=lr;i++)
a.push(ss[i]);
for(int i=rl;i<=rr;i++)
b.push(ss[i]);
while(a.size() and b.size())
{
if(cmp1(a.front(),b.front()))
{
c.push(a.front());
a.pop();
}
else
{
c.push(b.front());
b.pop();
}
}
while(a.size())
{
c.push(a.front());
a.pop();
}
while(b.size())
{
c.push(b.front());
b.pop();
}
for(int i=ll;i<=rr;i++)
{
ss[i]=c.front();
c.pop();
}
}
void D1(int l,int r)
{
if(l>=r)
return;
int mid=(l+r)>>1;
D1(l,mid+0);
D1(mid+1,r);
C1(l,mid,mid+1,r);
}
static inline int tri(int k)
{
return (k*(k+1)/2)+k*k;
}
int BS(int v)
{
int L=-1,R=17;
while(L+1<R)
{
int mid=(L+R)>>1;
if(tri(mid)<v)
L=mid;
else
R=mid;
}
return R;
}
void SR(int l,int r,const veci &inds)
{
if(inds.empty())
return;
if(l==r)
{
for(int id:inds)
ss[id]=l;
return;
}
int len=r-l+1;
int m=min(max(1,gw/max(1,(int)inds.size())),BS(r));
ZS(gn);
for(int id:inds)
tos[id]=m;
playRound(tos,res);
veci la,ra;
int lr=l-1;
for(int id:inds)
{
if(res[id]<=m)
{
la.pub(id);
lr++;
}
else
{
ra.pub(id);
}
}
if(la.size())
SR(l,lr,la);
if(ra.size())
SR(lr+1,r,ra);
}
void allValues(int n,int w,int *p)
{
gn=n;
gw=w;
if(w==2*n)
{
for(int i=0;i<n;i++)
ss[i]=i;
D1(0,n-1);
for(int i=0;i<n;i++)
p[ss[i]]=i+1;
}
else
{
veci inds;
inds.reserve(n);
for(int i=0;i<n;i++)
inds.pub(i);
SR(1,100,inds);
for(int i=0;i<n;i++)
p[i]=ss[i];
}
}
