#include "routers.h"
#include <bits/stdc++.h>
#define us use_detector
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
const int MAXN = 1e5+10;
int n, ma;
int a[1010], dis[1010]; // i ke i-1
set<int> le[MAXN], ri[MAXN];
int MN[MAXN], MX[MAXN], qu[MAXN];
int que(int mid){
if(qu[mid] != -1) return qu[mid];
for(int i=1; i<=n-1; i++)
if(MN[i] <= mid && mid <= MX[i]) return qu[mid] = i;
return qu[mid] = us(mid);
}
void find(int idx){
for(int i=1; i<=n-1; i++)
if(dis[i]!=-1 && a[i]!=-1) a[i] = dis[i]-a[i-1];
// int mx = 0, mn = ma+1;
// for(int i=0; i<=idx-1; i++) chmx(mx, a[i]);
// for(int i=idx+1; i<=n-1; i++)
// if(a[i] != -1) chmn(mn, a[i]);
// int l=mx+1, r=mn-1, mid=0;
// if(!le[idx].empty()) chmx(l, *--le[idx].end());
// if(!ri[idx].empty()) chmn(r, *ri[idx].begin());
// int cnt=l; l++;
int l=0, r=ma, mid=0, cnt=-1;
while(l<=r){
mid = md;
int ret = que(mid);
// chmn(MN[ret], mid); chmx(MX[ret], mid);
// for(int i=1; i<=ret-1; i++) ri[i].insert(mid);
// for(int i=ret+1; i<=n-1; i++) le[i].insert(mid);
if(ret < idx) cnt = mid, l = mid+1;
else r = mid-1;
}
dis[idx] = 2*cnt;
}
// void solve(int le, int ri){
// if(le>ri) return;
// // find(le);
// // solve(le+1, ri);
// int mid = (le+ri)>>1;
// find(mid);
// solve(le, mid-1); solve(mid+1, ri);
// }
std::vector<int> find_routers(int MA, int N, int q) {
n = N; ma = MA;
for(int i=0; i<=ma; i++) qu[i] = -1;
for(int i=1; i<=n-1; i++){
a[i] = -1; MN[i] = ma; MX[i] = -1; dis[i] = -1;
}
// if(n==1000){
// solve(1, 512);
// solve(513, 768);
// // solve(1, 768);
// solve(769, 999);
// } else solve(1, n-1);
for(int i=1; i<=n-1; i++) find(i);
vector<int> ans; ans.pb(0);
for(int i=1; i<=n-1; i++){
a[i] = dis[i]-a[i-1];
// cout << a[i] << " a\n";
ans.pb(a[i]);
assert(a[i] != -1);
}
// for(auto in : ans) cout << in << " in\n";
return ans;
}
