#include <bits/stdc++.h>
#include "books.h"
typedef long long ll;
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.
//
/* find the first element larger than A
* if there is none, set the index to N+1
*
*
*
*
*/
void solve(int N, int K, long long A, int S) {
int lo = 1, hi = N;
int idx=N;
vector<ll> arr; arr.assign(N+1,-1);
while(lo<=hi) {
int mid = (lo+hi)/2;
ll res = skim(mid);
arr[mid] = res;
if(res > A) {
hi=mid-1;
idx=min(idx,mid);
}
else {
lo=mid+1;
}
}
if(idx<K) {
impossible();
return;
}
ll total=arr[idx];
for(int i=1;i<K;i++) {
if(arr[i]==-1) arr[i] = skim(i);
total += arr[i];
}
if(A<=total && total<=2*A) {
vector<int> ans; for(int i=1;i<K;i++) ans.push_back(i);
ans.push_back(idx);
answer(ans);
return;
}
total-=arr[idx];
total+=arr[K];
set<int> ans;
for(int i=1;i<=K;i++) ans.insert(i);
if(idx==N && arr[N]<=A) {
idx++;
}
if(A<=total && total<=2*A) {
vector<int> ansv; for(int x: ans) ansv.push_back(x);
answer(ansv);
return;
}
for(int i=1;i<=K;i++) {
if(idx-i>K) {
if(arr[idx-i]==-1) arr[idx-i] = skim(idx-i);
total-= arr[i];
total+= arr[idx-i];
ans.insert(idx-i);
ans.erase(i);
}
//for(int x: ans) cout<<x<<" ";
//cout<<"\ntotal: "<<total<<"\n";
if(A<=total && total<=2*A) {
vector<int> ansv; for(int x: ans) ansv.push_back(x);
answer(ansv);
return;
}
}
impossible();
}
