#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){
int l = 1,r = n+1;
while(l < r){
int m = (l+r)/2;
if(skim(m) < a){
l = m + 1;
}
else r = m;
}
vector<pair<int,long long>> x;
vector<pair<int,long long>> y;
for(int i = 1;i<=k;i++){
x.push_back({i,skim(i)});
}
if(l < k){
impossible();
return;
}
if(l != n+1){
long long sum = skim(l);
for(int i = 0;i<k-1;i++){
sum += x[i].second;
}
if(a <= sum && sum <= 2*a){
vector<int> ret;
for(int i = 1;i<=k-1;i++){
ret.push_back(i);
}
ret.push_back(l);
answer(ret);
return;
}
}
if(l == k){
impossible();
return;
}
for(int i = k;i>=1;i--){
y.push_back({l-i,skim(l-i)});
}
long long sum = 0;
for(auto u:x){
sum += u.second;
}
if(a <= sum && sum <= 2*a){
vector<int> ret;
for(int i = 1;i<=k;i++){
ret.push_back(i);
}
answer(ret);
return;
}
if(sum > 2*a){
impossible();
return;
}
for(int i = 1;i<=k;i++){
sum -= x[k-i].second;
sum += y[k-i].second;
if(a <= sum && sum <= 2*a){
vector<int> ret;
for(int j = 1;j<=k-i;j++){
ret.push_back(i);
}
for(int j = k-1;j>=k-i;j--){
ret.push_back(y[j].first);
}
answer(ret);
sort(ret.begin(),ret.end());
return;
}
assert(sum < a);
}
impossible();
}
