#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
random_device rd;
mt19937 rng(rd());
template<class T>
T randomize(T mod)
{
return uniform_int_distribution<T>(0, mod - 1)(rng);
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= b; i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) x.begin(), x.end()
#define INF 1000000007
#define LLINF 2696969696969696969
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, Q;
vi arr, rec;
vi test = {8, 4, 2, 1};
vi ans;
vi ask(vi s)
{
int tmp[100], tmp1[100];
FOR(i, 0, N)
{
tmp[i] = s[i];
}
playRound(tmp, tmp1);
FOR(i, 0, N)
{
s[i] = tmp1[i];
}
return s;
}
int minValue(int n, int q)
{
N = n; Q = q; arr.resize(N);
arr[0] = 1;
rec = ask(arr);
FOR(i, 1, N)
{
if (rec[i] == 0) return i;
}
return 0;
}
int maxValue(int n, int q)
{
N = n; Q = q; arr.resize(N);
vi cands;
FOR(i, 0, N) cands.PB(i);
while(SZ(cands) > 1)
{
vi tmp;
FOR(i, 0, N) arr[i] = 0;
for (int x : cands) arr[x] = N / SZ(cands);
rec = ask(arr);
FOR(i, 0, N)
{
if (rec[i] > (N / SZ(cands))) tmp.PB(i);
}
cands = tmp;
// for (int x : cands)
// {
// cerr << x << ' ';
// }
// cerr << endl;
}
return cands[0];
}
bool cmp(int i, int j)
{
if (i == j) return false;
//is i < j?
FOR(k, 0, N) arr[k] = 0;
for (int x : test)
{
arr[i] = x; arr[j] = x;
rec = ask(arr);
if (rec[i] > x && rec[j] <= x) return false;
if (rec[i] <= x && rec[j] > x) return true;
}
return false;
}
int greaterValue(int n, int q)
{
N = n; Q = q; arr.resize(N);
//say you put x on each.
//they will put 98 on thhe other guys and 0 on both of you.
//they will put 99-x on the other guys and x+1 on one of you. it's a sacrifice of 1+2+...x-1. for you. but the next one needs x....2x-2
//they will put 98-2x on everybody else and x+1 on both of you.
//they put it on the more expensive of you two.
return cmp(0, 1);
}
bool cmp1(int a, int b)
{
//return true if a < b
FOR(i, 0, N)
{
arr[i] = 0;
}
arr[a] = N; arr[b] = N;
rec = ask(arr);
return (rec[b] > N);
}
vi ord[300];
void build4(int w, int L, int R)
{
ord[w].clear();
if (L == R)
{
ord[w].PB(L);
return;
}
int mid = (L + R) >> 1;
build4(w << 1, L, mid);
build4(w << 1 | 1, mid + 1, R);
}
void solve4(int w, int L, int R)
{
if (L == R) return;
int mid = (L + R) >> 1;
solve4(w << 1, L, mid);
solve4(w << 1 | 1, mid + 1, R);
int lt = 0, rt = 0;
while(lt < SZ(ord[w << 1]) || rt < SZ(ord[w << 1 | 1]))
{
if (rt == SZ(ord[w << 1 | 1]) || ((lt != SZ(ord[w << 1]) && cmp1(ord[w << 1][lt], ord[w << 1 | 1][rt]))))
{
ord[w].PB(ord[w << 1][lt]);
lt++;
}
else
{
ord[w].PB(ord[w << 1 | 1][rt]);
rt++;
}
}
}
void allValues(int n, int q, int *res)
{
N = n; Q = q; arr.resize(N); ans.resize(N);
if (Q == 2 * N)
{
build4(1, 0, N - 1);
solve4(1, 0, N - 1);
FOR(i, 0, SZ(ord[1]))
{
ans[ord[1][i]] = i + 1;
}
}
else
{
FOR(i, 0, N) arr[i] = 1;
rec = ask(arr);
vi upper, lower;
FOR(i, 0, N)
{
if (rec[i]) upper.PB(i);
else lower.PB(i);
}
FOR(i, 0, SZ(upper))
{
swap(upper[i], upper[randomize(i + 1)]);
}
FOR(i, 0, SZ(lower))
{
swap(lower[i], lower[randomize(i + 1)]);
}
sort(ALL(upper), cmp);
sort(ALL(lower), cmp);
ans = lower;
ans.insert(ans.end(), ALL(upper));
FOR(i, 0, N)
{
arr[ans[i]] = i + 1;
}
ans = arr;
}
//eh we only have N.
//well you know who the upper half is now.
FOR(i, 0, N) res[i] = ans[i];
return;
}
