#include <bits/stdc++.h>
#include "books.h"
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.
//
void solve(int N, int K, long long A, int S) {
long long sum = 0;
vector<long long> arr(N + 1, -1);
for(int l = 1; l < K; l++) {
arr[l] = skim(l);
sum += arr[l];
}
int lo = K, hi = N, ind = -1;
while(lo <= hi) {
int md = (lo + hi) / 2;
if(arr[md] == -1)
arr[md] = skim(md);
if(arr[md] > A) ind = md, hi = md - 1;
else lo = md + 1;
}
if(ind >= K && sum + arr[ind] >= A && sum + arr[ind] <= 2LL * A) {
vector<int> res;
for(int l = 1; l < K; l++) res.push_back(l);
res.push_back(ind);
answer(res); return;
}
if(arr[K] == -1) arr[K] = skim(K);
sum += arr[K];
if(sum >= A && sum <= 2LL * A) {
vector<int> res;
for(int l = 1; l <= K; l++) res.push_back(l);
answer(res); return;
}
if(ind == -1 || ind < 2 * K) ind = N + 1;
lo = 1, hi = ind - 1;
while(lo <= K) {
sum -= arr[lo];
if(arr[hi] == -1) arr[hi] = skim(hi);
sum += arr[hi];
if(sum >= A && sum <= 2LL * A) {
vector<int> res;
for(int l = lo + 1; l <= K; l++)
res.push_back(l);
for(int l = hi; l < ind; l++)
res.push_back(l);
answer(res); return;
}
lo++, hi--;
}
impossible();
}
