#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 = 1010;
int n, ma;
int a[1010], dis[1010]; // i ke i-1
set<int> le[MAXN], ri[MAXN];
int MN[MAXN], MX[MAXN];
int que(int mid){
for(int i=1; i<=n-1; i++)
if(MN[i] <= mid && mid <= MX[i]) return i;
return 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++;
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=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);
// if(n/2 != 0){
// find(n/2);
// for(int i=n/2+1; i<=n-1; i++) find(i);
// for(int i=n/2-1; i>=1; i--) find(i);
// } else {
// 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;
}
