#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.
//
typedef long long ll;
void solve(int N, int K, long long A, int S) {
// TODO implement this function
vector<ll> x(N + 1);
ll sum = 0;
for(int i = 1; i <= K; i++)
sum += x[i] = skim(i);
if(sum > 2 * A)
impossible();
sum -= x[K];
int l = K + 1, h = N, a = N + 1;
while(l <= h){
int mid = (l + h) / 2;
if(skim(mid) >= A){
h = mid - 1;
a = mid;
}
else
l = mid + 1;
}
if(a != N + 1){
sum += x[a] = skim(a);
if(sum <= 2 * A){
vector<int> ans;
for(int i = 1; i < K; i++)
ans.push_back(i);
ans.push_back(a);
answer(ans);
return;
}
}
for(int i = 0; i < K; i++)
x[a - i - 1] = skim(a - i - 1);
for(int i = 0; i <= K; i++){
sum = 0;
vector<int> ans;
for(int j = 1; j <= K - i; j++){
sum += x[j];
ans.push_back(j);
}
for(int j = 0; j < i; j++){
sum += x[a - j - 1];
ans.push_back(a - j - 1);
}
if(sum >= A && sum <= 2*A){
answer(ans);
return;
}
}
impossible();
}
