#include <bits/stdc++.h>
#include "books.h"
#define lli __int128_t
#define MP make_pair
#define pb push_back
using namespace std;
//
// --- 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.
//
vector<lli> dt;
lli skimmer(int x) {
if(dt[x] != -1) {
return dt[x];
}
return dt[x] = skim(x);
}
void solve(int N, int K, long long A, int S) {
dt.assign(N+1, (lli)-1);
vector<int> res;
lli sum = (lli) 0;
for(int i = 1; i<=K; i++) {
sum += skimmer(i);
}
if(sum > 2*A) impossible();
lli val = A;
int l = K, r = N;
while(l<r) {
int tm = (l + r) / 2;
if(val <= skimmer(tm)) {
r = tm;
}
else {
l = tm + 1;
}
}
sum -= skimmer(K);
if(val <= skimmer(l)) {
if(sum + skimmer(l) <= 2*A) {
res.clear();
for(int i = 1; i<=K-1; i++) res.pb(i);
res.pb(l);
answer(res);
}
}
else {
l++;
}
N = l - (lli)1;
sum = 0;
res.clear();
if(N < K) impossible();
for(int i = 1; i<=K; i++) {
sum += skimmer(i);
res.pb(i);
}
if(sum >= A) {
answer(res);
}
res.clear();
for(int i = K; i>=1; i--) {
sum -= skimmer(i);
sum += skimmer(N);
res.pb(N);
N--;
if(sum >= A) {
for(int j = 1; j<i; j++) {
res.pb(j);
}
answer(res);
}
}
impossible();
}
