#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();
if(sum >= A){
vector<int> ans(K);
for(int i = 1; i <= K; i++)
ans[i - 1] = i;
answer(ans);
}
sum -= x[K];
int l = K, h = N + 1, a = N;
while(l < h){
int mid = (l + h) / 2;
if(skim(mid) < A)
l = mid + 1;
else{
a = mid;
h = mid;
}
}
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);
}
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 = 0; j < K - i; j++){
sum += x[j];
ans.push_back(j + 1);
}
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);
}
impossible();
}
