#include <bits/stdc++.h>
#include "books.h"
using namespace std;
void solve(int N, int K, long long A, int S) {
vector<long long> know(N, -1);
auto ask = [&](int i) -> long long {
if (i < 0 || i > N) return 0LL;
if (know[i] == -1) {
know[i] = skim(i+1);
}
return know[i];
};
//find sum of smallest K-1
long long sum = 0;
for (int i = 0; i < K-1; i++) {
sum += ask(i);
if (sum > 2*A) {
impossible(); return;
}
}
// find last useful
int l = K-2, r = N;
while (l < r-1) {
int m = (l+r)/2;
if (sum + ask(m) <= 2*A) l = m;
else r = m;
}
if (r == K-1) {
impossible(); return;
}
sum += ask(l);
vector<int> ans(K);
iota(ans.begin(), ans.end(), 1);
ans.back() = l+1;
if(sum >= A) {
assert(sum <= 2*A);
answer(ans);
}
int j = 0;
while (sum < A && j < K-1) {
// if sum smaller than A then last useful is also smaller than A
// therefore by increasing by less than A every time I have to get a solution
if (l == K-1) {
impossible(); return;
}
sum -= ask(j);
ans[j++] = l--;
sum += ask(l);
if(sum >= A) {
assert(sum <= 2*A);
answer(ans);
}
}
impossible();
}
