// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
#include "koala.h"
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 200005
int minValue(int n, int w) {
int b[n], r[n];
REP (i, 0, n) {
b[i] = 0;
}
b[0] = 1;
playRound(b, r);
REP (i, 0, n) {
if (r[i] == 0) {
return i;
}
}
assert(0);
}
int maxValue(int n, int w) {
int b[n], r[n];
REP (i, 0, n) {
b[i] = 1;
}
playRound(b, r);
vi big;
REP (i, 0, n) {
if (r[i] > 1) {
big.pb(i);
}
}
while (big.size() > 1) {
int x = w / big.size();
REP (i, 0, n) {
b[i] = 0;
}
for (int i : big) {
b[i] = x;
}
playRound(b, r);
big.clear();
REP (i, 0, n) {
if (r[i] > 1) {
big.pb(i);
}
}
}
assert(big.size() == 1);
return big[0];
}
int greaterValue(int n, int w) {
int lo = 1, hi = min(w / 2, 8), mid;
while (lo <= hi) {
mid = lo + hi + 1 >> 1;
int b[n], r[n];
REP (i, 0, n) {
b[i] = 0;
}
b[0] = b[1] = mid;
playRound(b, r);
bool is0 = r[0] > mid, is1 = r[1] > mid;
if (is0 != is1) {
if (is0) {
return 0;
} else {
return 1;
}
}
if (is0) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
assert(0);
return 0;
}
int res[105];
template <class T>
void my_sort(int *arr, int l, int r, T &&f) {
int n = r - l;
if (n <= 1) return;
int m = l + r + 1 >> 1;
my_sort(arr, l, m, f);
my_sort(arr, m, r, f);
int a = l, b = m, c = l;
while (a < m && b < r) {
if (f(arr[a], arr[b])) {
res[c++] = arr[a++];
} else {
res[c++] = arr[b++];
}
}
while (a < m) {
res[c++] = arr[a++];
}
while (b < r) {
res[c++] = arr[b++];
}
REP (i, l, r) {
arr[i] = res[i];
}
}
void allValues(int n, int w, int *p) {
if (w == 2 * n) {
int id[n];
iota(id, id + n, 0);
my_sort(id, 0, n, [&] (int l, int r) {
int b[n], c[n];
REP (i, 0, n) {
b[i] = 0;
}
b[l] = b[r] = n;
playRound(b, c);
return c[l] <= n;
});
REP (i, 0, n) {
p[id[i]] = i + 1;
}
} else {
int id[n];
iota(id, id + n, 0);
my_sort(id, 0, n, [&] (int s, int e) {
int lo = 1, hi = min(w / 2, 8), mid;
while (lo <= hi) {
mid = lo + hi >> 1;
int b[n], r[n];
REP (i, 0, n) {
b[i] = 0;
}
b[s] = b[e] = mid;
playRound(b, r);
bool is0 = r[s] > mid, is1 = r[e] > mid;
if (is0 != is1) {
if (is0) {
return 0;
} else {
return 1;
}
}
if (is0) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
assert(0);
return 0;
});
REP (i, 0, n) {
p[id[i]] = i + 1;
}
}
}
