#include <bits/stdc++.h>
#include "books.h"
#include <vector>
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.
//
vector<ll> arr(1e5+5,-1);
ll get(int pos){
if(arr[pos] != -1)return arr[pos];
arr[pos] = skim(pos);
return arr[pos];
}
void submit(set<int> a){
vector<int> b;
for(int c:a)b.push_back(c);
answer(b);
}
void solve(int N, int K, long long A, int S) {
int l = 1,r = N;
while(l<=r){
int mid = (l+r)/2;
if(get(mid) <= A){
l = mid+1;
}else{
r = mid-1;
}
}
r = l;
l = K+1;
set<int> ans;
ll sm = 0;
for(int i=1;i<=K;i++){
sm += get(i);
ans.insert(i);
}
if(sm > 2*A){
impossible();
return;
}
if(sm <= 2*A && A <= sm){
submit(ans);
return;
}
while(sm < A){
if(r < l){
impossible();
return;
}
ll temp = sm + get(r) - get(*ans.begin());
if(temp > 2*A)r--;
else{
sm = temp;
ans.erase(ans.begin());
ans.insert(r);
}
}
while(sm > 2*A){
if(r < l){
impossible();
return;
}
ll temp = sm + get(l) - get(*ans.rbegin());
if(temp < A)l++;
else{
sm = temp;
ans.erase(prev(ans.end()));
ans.insert(l);
}
}
if(sm <= 2*A && A <= sm){
submit(ans);
return;
}
impossible();
}
