#include <bits/stdc++.h>
#include "books.h"
using namespace std;
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
typedef vector<ii> vii;
//
// --- 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) {
// TODO implement this function
vector<long long> V(N+5);
vector<int> ans;
for (int i=0; i<N+5; i++) V[i]=-1;
long long sum=0;
for (int i=1; i<=K; i++){
V[i]=skim(i);
sum+=V[i];
}
if (sum>2*A){
impossible();
}else if (sum>=A){
//answer!!
ans.clear();
for (int i=1; i<=K; i++){
ans.push_back(i);
}
answer(ans);
}else{
//sum<A
ans.clear();
//binary search from K+1 to N
ll L=1, R=N+1, M;
while (L<R) {
M = (L+R)/2;
ll temp;
if(V[M] != -1) temp = V[M];
else temp = skim(M);
V[M] = temp;
if (temp < A) L = M+1;
else R = M;
}
if (L < K) impossible();
if (L <= N){
ll temp;
if(V[L] != -1) temp = V[L];
else temp = skim(L);
V[L] = temp;
if(sum - V[K] + temp <= 2*A){
ans.clear();
for(int i=1; i<K; i++){
ans.push_back(i);
}
ans.push_back(L);
answer(ans);
}
N = L - 1;
}
set<int> S_;
for(int i=1; i<=K; i++){
S_.insert(i);
}
for(int i=0; i<K; i++){
S_.erase(K - i);
S_.insert(N - i);
ll temp;
if(V[N - i] != -1) temp = V[N - i];
else temp = skim(N - i);
V[N - i] = temp;
sum -= V[K - i];
sum += temp;
if(A <= sum && sum <= 2*A){
ans.clear();
for(int i : S_){
ans.push_back(i);
}
answer(ans);
}
}
impossible();
}
}
