#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
// books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ books_sample.cpp sample_grader.cpp
// in this folder.
//
const int maxn=1e5+5;
ll arr[maxn];
int now[20];
ll f(int idx){
if(!arr[idx]) arr[idx] = skim(idx);
return arr[idx];
}
void solve(int N, int K, long long A, int S) {
ll sum = 0;
for(int i = 1;i <= K;i++) sum += f(i),now[i] = i;
if(sum > 2 * A){
impossible();
return;
}
if(sum >= A){
vector<int>ans;
for(int i = 1;i <= K;i++) ans.push_back(i);
answer(ans);
return;
}
int l = K + 1,r = N,md,jog=-1;
while(l <= r){
md = (l + r) / 2;
if(sum - f(K) + f(md) <= 2*A) jog=md,l=md+1;
else r = md - 1;
}
if(jog == -1){
impossible();
return;
}
now[K] = jog;
sum -= f(K);
sum += f(jog);
if(sum >= A){
vector<int>ans;
for(int i = 1;i < K;i++) ans.push_back(i);
ans.push_back(jog);
answer(ans);
return;
}
int nw = jog-1;
for(int i = K-1;i >= 1;i--){
if(sum - f(i) + f(nw) <= 2*A){
now[i] = nw;
sum -= f(i);
sum += f(nw);
nw--;
}
else {
l = i + 1,r = nw - 1,jog=-1;
while(l <= r){
md = (l + r) / 2;
if(sum - f(i) + f(md) <= 2*A) jog=md,l=md+1;
else r=md-1;
}
now[i] = jog;
sum -= f(i);
sum += f(jog);
}
if(sum >= A){
vector<int>ans;
for(int i = 1;i <= K;i++) ans.push_back(now[i]);
answer(ans);
return;
}
}
}
